Prime factorization algorithm

A prime factorization algorithm is any 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. 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.

Contents

1 A simple factorization algorithm

1.1 Description
1.2 Example

1.2.1 Code

1.3 Time complexity

2 External link

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 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:

 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
 
 ListOfPrimes=[2,3,5,7,11,13,17,19]
 maxindex=len(ListOfPrimes)
 maxprimeinlist=ListOfPrimes[-1]
 
 # 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 a integer number """
   primes = []
   index=0
   candidate = ListOfPrimes[index]
   while not primes and candidate <= n:
     if n%candidate == 0 and (index < maxindex or isPrime(candidate)):
       primes = primes + [candidate] + factorize(n//candidate)
     index += 1            
     if index < maxindex:
       candidate = ListOfPrimes[index]
     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(prime) + '^' + str(count)]
       prime,count=x,1
   list = list + [str(prime) + '^' + str(count)]
   return list
 
 if __name__ == '__main__':
   print condense(factorize(long(sys.argv[1])))
 
 # Sample output
 #
 # python factorize.py 173248246132375748867198458668657948626531982421875
 # ['3^24', '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.