TOPICS
Search

Pollard p-1 Factorization Method


A prime factorization algorithm which can be implemented in a single-step or double-step form. In the single-step version, a prime factor p of a number n can be found if p-1 is a product of small primes by finding an m such that

 m=c^q (mod n),

where p-1|q, with q a large number and (c,n)=1. Then since p-1|q, m=1 (mod p), so p|m-1. There is therefore a good chance that nm-1, in which case GCD(m-1,n) (where GCD is the greatest common divisor) will be a nontrivial divisor of n.

In the double-step version, a prime factor p can be found if p-1 is a product of small primes and a single larger prime.


See also

Prime Factorization Algorithms, Williams p+1 Factorization Method

Explore with Wolfram|Alpha

References

Bressoud, D. M. Factorization and Primality Testing. New York: Springer-Verlag, pp. 67-69, 1989.Pollard, J. M. "Theorems on Factorization and Primality Testing." Proc. Cambridge Phil. Soc. 76, 521-528, 1974.

Referenced on Wolfram|Alpha

Pollard p-1 Factorization Method

Cite this as:

Weisstein, Eric W. "Pollard p-1 Factorization Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Pollardp-1FactorizationMethod.html

Subject classifications