To factorize n, find a non-trivial square root of 1 mod n

Quick description

If you can find a non-trivial square root of $1$ mod $n$ , then you can find a non-trivial factor of $n$ .

General discussion

If $p$ is prime, then the equation $x^2\equiv 1$ mod $p$ has the two solutions $x\equiv\pm 1$ mod $p$ . But if $n$ is composite, then the equation can have more solutions. For instance, if $n=15$ then $x$ can be $\pm 1$ or $\pm 4$ . Indeed, if $n=pq$ for two odd primes $p$ and $q$ , then $1$ will always have four square roots, since $x^2\equiv 1$ mod $pq$ if and only if $x^2\equiv 1$ mod $p$ and $x^2\equiv 1$ mod $q$ , by the Chinese remainder theorem, and each of the four of the pairs of equations $x\equiv\pm 1$ mod $p$ and $x\equiv\pm 1$ mod $q$ has a unique solution, also by the Chinese remainder theorem. (This explains the square roots of $1$ mod $15$ , for example.)

We can also turn this idea round. If you are given $x$ such that $x^2\equiv 1$ mod $n$ and $x\not\equiv\pm 1$ mod $n$ , then you can find a factor of $n$ . To do so, you observe first that $(x+1)(x-1)\equiv 0$ mod $n$ , so $n$ is a factor of $(x+1)(x-1)$ . This implies that $n$ has a non-trivial common factor with at least one of $x+1$ and $x-1$ , since neither is a multiple of $n$ . One can then apply Euclid's algorithm to find this common factor. (The idea of applying Euclid's algorithm in a situation like this is discussed in more detail in the article To find a factor of $n$ , find some $m$ such that $(m,n)$ is not $1$ .)