The Theory

Theorem: Given a non-prime integer n,

if x2 ? y2 mod n, and x ? ? y mod n,

then GCD(x+y, n) is a proper factor of n,

and so is GCD(x?y, n).

Previous slide

Next slide

Back to first slide

View graphic version