Main Page | See live article | Alphabetical index A prime factorization algorithm is an algorithm (a step-by-step process) by which an integer (whole number) is "decomposed" into a product of factors that are prime numbers. The Fundamental Theorem of Arithmetic guarantees that this decomposition is unique. Table of contents 1 A simple factorization algorithm 1.1 Description 1.2 Time complexity 2 External link A simple factorization algorithm Description We can describe a recursive algorithm to perform such factorizations: given a number n if n is prime, this is the factorization, so stop here. if n is composite, divide n by the first prime p1. If it divides cleanly, recurse with the value n/p1. If it does not divide cleanly, divide n by the next prime p2, and so on. Note we need only primes p1 to p√n. Time complexity The described algoithm works fine for small n. However, for an 18-digit number (which has 60 digits in binary), all primes below about 1,000,000,000 may need to be tested, which is taxing even for a computer. Adding two decimal digits to the original number will multiply the computation time by 10. The difficulty (large time complexity) of factorization makes it a suitable basis for modern cryptography. See also: Euler's Theorem, Integer factorization External link Prime factorization at Mathworld This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.