Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Tommy Jensen
Posts:
249
From:
Daegu, Korea
Registered:
12/6/09


Bounded modular square roots
Posted:
Jun 24, 2014 8:26 AM


Given input (a,N,c), all natural numbers, it is NPcomplete to decide whether there exists an integer x with 0 < x < c for which x^2 = a (mod N) holds, i.e. x is a square root of a modulo N, which is less than a constant c. Even if the prime factorization of N is known. This follows from a paper by Adleman and Manders in 1978.
Is it possible to remove a from the input, and preserve the NPcompleteness?
Say, how about the problem, with input (N,c), whether there exists an integer x with 0 < x < c for which x^2 = 2 (mod N) holds?
Or as a natural variation, whether there exists an integer x with 1 < x < c for which x^2 = 1 (mod N) holds?
Either problem is at least as hard as to find a trivial factor of N, by a simple argument. But are they also NPhard?



