TOPICS
Search

Prime Factorization Algorithms

Prime factorization algorithms determine the prime factors of a given positive integer, a process called prime factorization. The methods differ in their sophistication and computational complexity. General-purpose algorithms address arbitrary inputs, whereas additional information about the integer or its prime factors can reduce the work.

The simplest method of finding factors is so-called "direct search factorization" (a.k.a. trial division). In this method, all possible factors are systematically tested using trial division to see if they actually divide the given number. It is practical only for very small numbers.

The Pollard-Strassen method is a classical deterministic algorithm (Pomerance 1982, Hardy et al. 1990). For an integer N>=2, Harvey (2021) gave a deterministic algorithm with bit complexity

O(N^(1/5)(lnN)^(16/5)),

where O denotes big-O notation and ln is the natural logarithm. Harvey and Hittmeir (2022) improved this to

O((N^(1/5)(lnN)^(16/5))/((lnlnN)^(3/5))).

Rudich and Rousseau (2026) reported a further improvement to N^(o(1)) steps for computing the least prime factor, where o denotes little-o notation. Repeated calls would give complete prime factorization with the same asymptotic bound, although this last step was not formalized. Claude Opus 5.5 generated the ideas and Lean proof, and the authors audited the formal statement but did not read the proof. As of Oct. 31, 2026, the authors reported successful Lean checking, but independent specialist verification had not been reported.

See also

Brent's Factorization Method, Continued Fraction Factorization Algorithm, Direct Search Factorization, Dixon's Factorization Method, Elliptic Curve Factorization Method, Euler's Factorization Method, Excludent Factorization Method, Fermat's Factorization Method, Least Prime Factor, Legendre's Factorization Method, Number Field Sieve, Pollard p-1 Factorization Method, Pollard rho Factorization Algorithm, Prime Factorization, Prime Number, Quadratic Sieve, Quiteprime, Trial Division, Veryprime, Williams p+1 Factorization Method Explore this topic in the MathWorld classroom

Explore with Wolfram|Alpha

References

Anderson, D. D. (Ed.). Factorization in Integral Domains. New York: Dekker, 1997.Bressoud, D. M. Factorization and Primality Testing. New York: Springer-Verlag, 1989.Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of bn±1, b=2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, rev. ed. Providence, RI: Amer. Math. Soc., liv-lviii, 1988.Dickson, L. E. "Methods of Factoring." Ch. 14 in History of the Theory of Numbers, Vol. 1: Divisibility and Primality. New York: Dover, pp. 357-374, 2005.Hardy, K.; Muskat, J. B.; and Williams, K. S. "A Deterministic Algorithm for Solving n=fu^2+gv^2 in Coprime Integers u and v." Math. Comput. 55, 327-343, 1990.Harvey, D. "An Exponent One-Fifth Algorithm for Deterministic Integer Factorisation." Math. Comput. 90, 2937-2950, 2021. https://doi.org/10.1090/mcom/3658.Harvey, D. and Hittmeir, M. "A Log-Log Speedup for Exponent One-Fifth Deterministic Integer Factorisation." Math. Comput. 91, 1367-1379, 2022. https://doi.org/10.1090/mcom/3708.Herman, P. "The Factoring Page!" https://frenchfries.net/paul/factoring/.Lenstra, A. K. and Lenstra, H. W. Jr. "Algorithms in Number Theory." In Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (Ed. J. van Leeuwen). New York: Elsevier, pp. 673-715, 1990.Odlyzko, A. M. "The Complexity of Computing Discrete Logarithms and Factoring Integers." §4.5 in Open Problems in Communication and Computation (Ed. T. M. Cover and B. Gopinath). New York: Springer-Verlag, pp. 113-116, 1987.Odlyzko, A. M. "The Future of Integer Factorization." CryptoBytes: The Technical Newsletter of RSA Laboratories 1, No. 2, 5-12, 1995.Pomerance, C. "Analysis and Comparison of Some Integer Factorization Algorithms." In Computational Methods in Number Theory, Part 1 (Ed. H. W. Lenstra and R. Tijdeman). Amsterdam, Netherlands: Mathematisch Centrum, pp. 89-139, 1982.Pomerance, C. "Fast, Rigorous Factorization and Discrete Logarithm Algorithms." In Discrete Algorithms and Complexity (Ed. D. S. Johnson, T. Nishizeki, A. Nozaki, and H. S. Wilf). New York: Academic Press, pp. 119-143, 1987.Pomerance, C. "A Tale of Two Sieves." Not. Amer. Math. Soc. 43, 1473-1485, 1996.Riesel, H. "Algebraic Factors." Appendix 6 in Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 304-316, 1994.Rudich, I. and Rousseau, L.-M. "Deterministic Factoring in Time N^(o(1))." Oct. 29, 2026. https://hexagonmath.org/2610.00600v1.Weisstein, E. W. "Books about Prime Numbers." http://www.ericweisstein.com/encyclopedias/books/PrimeNumbers.html.Williams, H. C. and Shallit, J. O. "Factoring Integers Before Computers." In Mathematics of Computation 1943-1993, Fifty Years of Computational Mathematics (Ed. W. Gautschi). Providence, RI: Amer. Math. Soc., pp. 481-531, 1994.

Referenced on Wolfram|Alpha

Prime Factorization Algorithms

Cite this as:

Weisstein, Eric W. "Prime Factorization Algorithms." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/PrimeFactorizationAlgorithms.html

Subject classifications