Prime factorization algorithm
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.
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. Add p1 to the list of factors obtained for n/p1 to get a factorization for n. If it does not divide cleanly, divide n by the next prime p2, and so on.
Note that we need to test only primes pi such that pi ≤ √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 by is 11. 143/11 = 13. 13 is itself prime.
Thus working back, we have 9438 = 2*3*11*11*13
Here is the example in python:
import math,sys def factorize(n): def isPrime(n): return not [x for x in xrange(2,int(math.sqrt(n))) if n%x == 0] primes = [] candidates = xrange(2,n+1) candidate = 2 while not primes and candidate in candidates: if n%candidate == 0 and isPrime(candidate): primes.append(candidate) primes = primes + factorize(n/candidate) candidate += 1 return primes print factorize(int(sys.argv[1]))
output:
python factorize.py 9438 [2, 3, 11, 11, 13]
Time complexity
The algorithm 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