1
$\begingroup$

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

  • 4
    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.2012-10-15
  • 1
    If $N$ is prime, either http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm or http://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.2012-10-15
  • 0
    Special-case of [this question,](http://math.stackexchange.com/q/14501/242) on k'th roots. It's no easier than the general case.2012-10-15

0 Answers 0