Prime factorization algorithm

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.

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 p₁. If it divides cleanly, recurse with the value n/p₁. Add p₁ to the list of factors obtained for n/p₁ to get a factorization for n. If it does not divide cleanly, divide n by the next prime p₂, and so on.

Note that we need to test only primes p_i such that p_i ≤ √n.

Example

Suppose we wish to factorize 9438. 9438/2 = 4719, with no remainder so 2 is a factor. We repeat the algorithm with 4719. 4719/2 = 2359.5, so 2 is not a factor. 4719/3 = 1573, so three is a factor. The first prime 1573 is divisible by is 11. 1573/11 = 143. Similarly the first prime 143 is divisible is 11. 143/11 = 13. 13 is itself prime.

Thus working back, we have 9438 = 2*3*11*11*13

Time complexity

The algoithm described above works fine for small n, but becomes impractical as n gets larger. For example, for an 18-digit (or 60 bit) number, 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, Trial division