info prev up next book cdrom email home

Prime Cut

Find two numbers such that $x^2\equiv y^2\ \left({{\rm mod\ } {n}}\right)$. If you know the Greatest Common Divisor of $n$ and $x-y$, there exists a high probability of determining a Prime factor. Taking small numbers $x$ which additionally give small Primes $x^2\equiv p\ \left({{\rm mod\ } {n}}\right)$ further increases the chances of finding a Prime factor.

© 1996-9 Eric W. Weisstein