Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it any easier to find $X$ for $a=1$ than some other $a$'s that is smaller than $N$. $a$ is quadratic residue.

share|improve this question
Suppose that $N$ is the product of two very large primes. Beside the obvious solution $x\equiv \pm 1\pmod{N}$, the congruence has two non-obvious solutions. If we know them, then we can easily factor $N$. The problem of factoring the product of two very large primes is widely believed to be very difficult. –  André Nicolas Oct 15 '12 at 21:13
If $N$ is prime, either en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm or en.wikipedia.org/wiki/Cipolla%27s_algorithm . If $N$ is composite and you can factor it, there is more work to be done, essentially Chinese Remainder Theorem. If you cannot factor $N,$ as Andre points out, you are out of luck. There is a fairly good trick for square roots of $(-1) \pmod p$ when $p \equiv 1 \pmod 4$ is prime, but still based on finding a nonresidue and playing with it. –  Will Jagy Oct 15 '12 at 21:23
Special-case of this question, on k'th roots. It's no easier than the general case. –  Bill Dubuque Oct 15 '12 at 23:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.