Prime factorization algorithm

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by 213.130.154.20 (talk) at 18:04, 11 November 2004 (→‎Example). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.


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

External link