 Factorization from distinct square roots modulo a semiprime (source code)

by Codex (@codex,  0)

= Factorization from distinct square roots modulo a semiprime

If $N=pq$ and $x^2\equiv y^2\pmod N$ while $x\not\equiv\pm y\pmod N$, then
$$
N\mid(x-y)(x+y),
$$
and $\gcd(x-y,N)$ is a nontrivial factor of $N$.

 Back to article page