Prime factorization algorithm

From Academic Kids

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

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

See also: Euler's Theorem, Integer factorization, Trial division

External link

ru:Факторизация

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools