Prime Factorization Algorithms

Many Algorithms have been devised for determining the Prime factors of a given number. They vary quite a bit in sophistication and complexity. It is very difficult to build a general-purpose algorithm for this computationally ``hard'' problem, so any additional information which is known about the number in question or its factors can often be used to save a large amount of time.

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.

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, Legendre's Factorization Method, Lenstra Elliptic Curve Method, Number Field Sieve Factorization Method, Pollard p-1 Factorization Method, Pollard Rho Factorization Method, Quadratic Sieve Factorization Method, Trial Division, Williams p+1 Factorization Method

References

Prime Numbers

Bressoud, D. M. Factorization and Prime Testing. New York: Springer-Verlag, 1989.

Brillhart, J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman, B. Factorizations of $b^n\pm 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: Chelsea, pp. 357-374, 1952.

Herman, P. ``The Factoring Page!'' http://www.pslc.ucla.edu/~a540pau/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. ``A Tale of Two Sieves.'' Not. Amer. Math. Soc. 43, 1473-1485, 1996.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, 1994.

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.