View Single Post
Old 2021-07-31, 02:13   #20
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

3·1,999 Posts

Originally Posted by RomanM View Post
b=mod(u^n,p); a=mod(b^n,p)
b^2-a is a multiple of p for any integer n>0, I don't know the behavior of epsilon for every n, but seems that algorithm work only if n=2.
Do you mean b^n - a?

Another issue arises if n > 2, particularly for odd n > 2. Even if p is prime, if gcd(n, p-1) = 1, every residue mod p is an nth power residue. For n = 3, this is the case for every prime p congruent to 2 (mod 3).
Dr Sardonicus is offline   Reply With Quote