Detecting bigInt roots

[mathPuzzles]

Is there any screening/probabilistic test to speed up the determination of whether a given value x is a square root of 1 mod N, other than just doing the \(x^2\mod N\) expansion explicitly? x and N are bigints of thousands or more bits, so that multiplication can be expensive.

Certainly there's a couple trivial pretests.. we can test if x=1 or N-1 and return true if it is. We can then follow up with a test if \(x<\sqrt N\) which is also nearly free since we can just compare the binary bit counts of x compared to N, and return false if x is too small.

I can't think of any other shortcuts beyond this.

[alpertron]

If you know that N is prime, checking that x=1 or x=N-1 is enough. You cannot find other value of x such that x² = 1 (mod N).

If N is composite and you know the prime factors p_i of N, you can check whether x = 1 or x = p_i-1 (mod p_i) for all values of i. If the congruence does not hold for some value of i, that means that x² is not 1 (mod N).

[Dr Sardonicus]

Originally Posted by mathPuzzles

Is there any screening/probabilistic test to speed up the determination of whether a given value x is a square root of 1 mod N, other than just doing the \(x^2\mod N\) expansion explicitly? x and N are bigints of thousands or more bits, so that multiplication can be expensive.

Certainly there's a couple trivial pretests.. we can test if x=1 or N-1 and return true if it is. We can then follow up with a test if \(x<\sqrt N\) which is also nearly free since we can just compare the binary bit counts of x compared to N, and return false if x is too small.

I can't think of any other shortcuts beyond this.

Well, if x^2 == 1 (mod N) and x =/= 1 or -1 (mod N), then taking

gcd(x - 1, N) and gcd(x + 1, N)

should produce a proper factorization of N...

[science_man_88]

Originally Posted by Dr Sardonicus

Well, if x^2 == 1 (mod N) and x =/= 1 or -1 (mod N), then taking

gcd(x - 1, N) and gcd(x + 1, N)

should produce a proper factorization of N...

Is not always true... example N=9 and x=8, 8 is -1 mod 9; 8^2 is 1 mod 9; gcd(8+1,9)==9; gcd(8-1,9)==1 .You don't get anything about 3 being a factor, so in theory you could conclude 9 is prime. Same thing happens, with x=14 and N=15 x-1 is prime so gcd(x-1,N)==1 and x+1 is N. okay didn't see the not equal sign for some reason. at least this post shows why the not equals sign is there.

[CRGreathouse]

Originally Posted by science_man_88

Is not always true... example N=9 and x=8

But then x = -1 mod N, so Dr Sardonicus' condition doesn't hold and his (?) conclusion need not follow.

[a1call]

Stating the obvious in case it is of any use.
N=x^2-1 -> x-1 | N

Or more generally
N=x^m - y^m -> x-y | N

--------

N=x^2+1 -> x+i | N

Or more generally
N=x^m + y^m -> x+y | N for all positive odd integers m

[science_man_88]

Originally Posted by CRGreathouse

But then x = -1 mod N, so Dr Sardonicus' condition doesn't hold and his (?) conclusion need not follow.

yeah I see that and posted the edit about this is part of why the not -1 or 1 mod N part needed to happen.

[mathPuzzles]

Originally Posted by alpertron

If N is composite and you know the prime factors p_i of N, you can check whether x = 1 or x = p_i-1 (mod p_i) for all values of i. If the congruence does not hold for some value of i, that means that x² is not 1 (mod N).

Let's extend that into an actual test for arbitrary N. It's not practical to factor N, but we could pull out SMALL factors. So we test N for small prime factors of say < 1000, using a O(log N) word-based division algorithm, then check those small residuals for 1 or -1 as you say.
For random N, this will indeed be a fast rejection for the majority of cases without ever having to do the expensive full multiplication.

[alpertron]

There is an optimum bound depending on the size of N. If N is very high (several thousands of bits), you can increase the bound.

If N has only 100 bits, you will need to reduce the bound, otherwise it will be cheaper to compute x² mod N than the multiple one-limb divisions.

[LaurV]

There is no known way to test faster a much-much-much weaker condition: the fact that x^2=a^2 (mod n), for which your question is a particular case* of a particular case**. If you would be able to do that, than you could efficiently factor n, because x^2-a^2=0 (mod n) and you could take gcd between n and either x+a or x-a.
--------------
*(where you do not take the modulus)
**(a=1)