Prime factorization algorithm

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.

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

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.

Code

Here is some code in Python for finding the factors of numbers less than 2147483647:

import sys
from math import sqrt
def factorize(n):
    def isPrime(n):
        return not 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 + ^* + factorize(n/candidate)
        candidate += 1            
    return primes
print factorize(int(sys.argv^*))

output:

python factorize.py 9438
3, 11, 11, 13

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

import sys
ListOfPrimes=^*
maxindex=len(ListOfPrimes)
maxprimeinlist=ListOfPrimes^*
 Put Primes in a dictionary
DictPrime={}
DictPrime.fromkeys(ListOfPrimes,True)
def intsqrt(n):
  """ Return the integer square root of a long number """
  def intsqrt_core(digitpair,remainder,results):
    # function intsqrt_core returns (results,remainder)
    if digitpair<100:
      currvalue=remainder*100 + digitpair
      for d in range(9,-1,-1):
        x=(2*10*results + d)*d
        if x <= currvalue:
          remainder= currvalue - x
          results=results*10 + d
          return(results,remainder)
    else:
      (results,remainder)=intsqrt_core(digitpair//100,remainder,results)
      (results,remainder)=intsqrt_core(digitpair%100,remainder,results)
      return(results,remainder)
  (results,remainder)=intsqrt_core(n,0,0)
  return results
def isPrime(n):
  """ Return True if n is a prime """
  if DictPrime.has_key(n):
    return True
  high=intsqrt(n)
  for x in ListOfPrimes:
    if x <= high and n%x == 0:
      return False
    if x >= high:
      return True
  x=maxprimeinlist + 2
  while x<=high:
    if n%x == 0:
      return False
    x += 2
  return True
def factorize(n):
  """ Factorize an integer number """
  primes = ^*
  index=0
  candidate = ListOfPrimes^*
  while not primes and candidate <= n:
    if n%candidate == 0 and (index < maxindex or isPrime(candidate)):
      primes = primes + ^* + factorize(n//candidate)
    index += 1            
    if index < maxindex:
      candidate = ListOfPrimes^*
    else:
      candidate += 2
  return primes
def condense(L):
  """ Condense result in list to prime^nth_power format """
  prime,count,list=0,0,^*
  for x in L:
    if x == prime:
      count += 1
    else:
      if prime != 0:
        list = list + + '^' + str(count)
      prime,count=x,1
  list = list + + '^' + str(count)
  return list
if __name__ == '__main__':
  print condense(factorize(long(sys.argv^*)))
 Sample output

 python factorize.py 173248246132375748867198458668657948626531982421875
 '5^14', '7^33', '13^1'

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.

External links

Prime factorization at Mathworld
Factorization solver implementing the algorithm described here, work shown
Factorizer Windows software to decompose numbers up to 2,147,483,646 into their prime constituents
Factoris, online prime factorizer

Integer factorization algorithms

Primfaktorzerlegung | Factorisation en nombres premiers | Факторизация