 Factorization from distinct square roots modulo a semiprime

ID: factorization-from-distinct-square-roots-modulo-a-semiprime

N = pq

and

x^{2} \equiv y^{2} (mod N)

while

x \neq \equiv \pm y (mod N)

, then

N ∣ (x - y) (x + y),

and

g cd (x - y, N)

is a nontrivial factor of

N

 New to topics? Read the docs here!