There is a comparison a^p0 = 1 (mod p) , where p0 and p are known are large prime numbers.

You need to programmatically find any a > 1 .

A simple iteration of a takes a very long time. Is there a faster option to find at least one solution?

  • There are algorithms for calculating radicals in a finite field. This is solved primarily mathematically. - typemoon

1 answer 1

Found the answer.

One must choose a random h from (1; p - 1).

Then with a sufficiently high probability x = h ^ [(p-1) / p0] mod p will fit the condition x ^ p0 = 1 (mod p).