Prime factorization algorithm

From Wikipedia, the free encyclopedia

A prime factorization algorithm is any algorithm by which an integer (whole number) is "decomposed" into a product of factors that are prime numbers (see prime factor). The fundamental theorem of arithmetic guarantees that this decomposition is unique. This article gives a simple example of an algorithm, which works well for numbers whose prime factors are small; faster algorithms for numbers with larger prime factors are discussed in the article on integer factorization. A 'fast' algorithm (which can factorise large numbers in a reasonably small time) is much sought after.

1 A simple factorization algorithm
2 See also
3 External links

[edit] A simple factorization algorithm

[edit] 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 \le \sqrt{n}$ .

[edit] Example

Suppose we wish to factorize the number 9438.

9438/2 = 4719 with a remainder of 0, so 2 is a factor of 9438. We repeat the algorithm with 4719.

4719/2 = 2359 with a remainder of 1, so 2 is NOT a factor of 4719. We try the next prime, 3.

4719/3 = 1573 with a remainder of 0, so 3 is a factor of 4719. We repeat the algorithm with 1573.

1573/3 = 524 with a remainder of 1, so 3 is NOT a factor of 1573. We try the next prime, 5.

1573/5 = 314 with a remainder of 3, so 5 is NOT a factor of 1573. We try the next prime, 7.

1573/7 = 224 with a remainder of 5, so 7 is NOT a factor of 1573. We try the next prime, 11.

1573/11 = 143 with a remainder of 0, so 11 is a factor of 1573. We repeat the algorithm with 143.

143/11 = 13 with a remainder of 0, so 11 is a factor of 143. We repeat the algorithm with 13.

13/11 = 1 with a remainder of 2, so 11 is NOT a factor of 13. We try the next prime, 13.

13/13 = 1 with a remainder of 0, so 13 is a factor of 13. We stop when we reached 1.

Thus working from top to bottom, we have 9438 = 2 × 3 × 11 × 11 × 13.

[edit] Code

Here is some code in Python for finding the factors of numbers less than 2,147,483,647 (the positive range of a 32-bit signed integer):

import sys
from math import sqrt
def factorize(n):
    def isPrime(n):
        return not [x for x in xrange(2,int(sqrt(n))+1) 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 = primes + [candidate] + factorize(n/candidate)
        candidate += 1            
    return primes
print factorize(int(sys.argv[1]))

output:

python factorize.py 9438
[2, 3, 11, 11, 13]

Here is more complex code in Python for finding the factors of any arbitrarily large number:

import sys
from itertools import groupby

_primeslist = [2, 3, 5, 7, 11, 13, 17, 19]
_primeset = set(_primeslist)

def intsqrt(n):
    """intsqrt(n): integer square root of a long number."""
    def intsqrt_core(digitpair, remainder, results):
        if digitpair < 100:
            currvalue = remainder * 100 + digitpair
            for d in xrange(9, -1, -1):
                x = (2 * 10 * results + d) * d
                if x <= currvalue:
                    remainder = currvalue - x
                    results = results * 10 + d
                    return results, remainder
        else:
            div, rem = divmod(digitpair, 100)
            results, remainder = intsqrt_core(div, remainder, results)
            results, remainder = intsqrt_core(rem, remainder, results)
            return results, remainder
    results, remainder = intsqrt_core(n, 0, 0)
    return results

def isPrime(n):
    """Return True if n is prime."""
    if n in _primeset:
        return True
    high = intsqrt(n)
    for x in _primeslist:
        if x <= high and not(n % x):
            return False
        if x >= high:
            return True
    x = _primeslist[-1] + 2
    while x <= high:
        if not(n % x):
            return False
        x += 2
    return True

def allfactors(n):
    """allfactors(n): return the list of all the prime factors of n."""
    maxindex = len(_primeslist)
    primes = []
    index = 0
    candidate = _primeslist[index]
    while not primes and candidate <= n:
        if not(n % candidate) and (index < maxindex
                                   or isPrime(candidate)):
            primes.append(candidate)
            primes.extend(allfactors(n // candidate))
        index += 1
        if index < maxindex:
            candidate = _primeslist[index]
        else:
            candidate += 2
    return primes

def factors(n):
    """Condensed prime factors list in [power, nth_power] format."""
    result = []
    for prime, prime_group in groupby(allfactors(n)):
        npower = 0
        for _ in prime_group:
            npower += 1
        result.append([prime, npower])
    return result

if __name__ == '__main__':
    print factors( int(sys.argv[1]) )

# Sample output:
#
# python factorize.py 173248246132375748867198458668657948626531982421875
# [[3, 24], [5, 14], [7, 33], [13, 1]]
# python factorize.py 10969629647
# [[104729, 1], [104743, 1]]

[edit] 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.