|
|
Prime Factorization AlgorithmA 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. 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. We repeat the algorithm with 4719.
- 4719/2 = 2359 with a remainder of 1, so 2 is NOT a factor.
- 4719/3 = 1573 with a remainder of 0, so 3 is a factor. We repeat the algorithm with 1573.
- The first prime number which 1573 is divisible by is the prime number 11.
- 1573/11 = 143 with a remainder of 0, so 11 is a factor. We repeat the algorithm with 143.
- Similarly 11 is the first prime number which 143 is divisible by.
- 143/11 = 13 with a remainder of 0, so 11 is a factor. We repeat the algorithm with 13.
- 13/13 = 1 with a remainder of 0, so 13 is a factor. We stop when we reached 1.
Thus working from top to bottom, we have 9438 = 2*3*11*11*13 Code Here is the code in Python for finding the factors of numbers less than 2147483647: 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 + candidate + factorize(n/candidate) candidate += 1 return primes print factorize(int(sys.argv1)) output: python factorize.py 9438 3, 11, 11, 13 Here is a 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 = ListOfPrimesindex 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 = ListOfPrimesindex 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.argv1))) - 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. See also: Euler's Theorem, Integer factorization, Trial division External link
|
 |