Prime factorization algorithm

Encyclopedia : P : PR : PRI : 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.

Contents

1 A simple factorization algorithm

1.1 Description
1.2 Example

1.2.1 Code

1.3 Time complexity

2 See also
3 External links

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

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 [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 dictionaryDictPrime=
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[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  == '':
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.

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

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.