TOPICS
Search

Prime Cut


Find two numbers such that x^2=y^2 (mod n). 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=p (mod n) further increases the chances of finding a prime factor.


See also

Greatest Common Divisor

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Prime Cut." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/PrimeCut.html

Subject classifications