A Simple Python Program for Factoring…

June 28, 2009 | Computer Science, Cryptography, Math | By: Mark VandeWettering

Sometimes, your interests converge. Over on Programming Praxis, he had a coding challenge to implement Monte Carlo factorization. The last couple of days, I have been thinking a bit more about factorization, so it seemed like a good idea to give it a whack. I cribbed a version of the Rabin Miller primality tester off the web, and then coded the rest up in python.

#!/usr/bin/env python

# 
# a basic implementation of the Pollard rho factorization
# Written by Mark VandeWettering <markv@pixar.com>
#

import sys
import locale
import random

class FactorError(Exception):
    def __init__(self, value):
	self.value = value 
    def __str__(self):
	return repr(self.value)

def miller_rabin_pass(a, n):
    d = n - 1
    s = 0
    while d % 2 == 0:
        d >>= 1
        s += 1

    a_to_power = pow(a, d, n)
    if a_to_power == 1:
        return True
    for i in xrange(s-1):
        if a_to_power == n - 1:
            return True
        a_to_power = (a_to_power * a_to_power) % n
    return a_to_power == n - 1

def isprime(n):
    for repeat in xrange(20):
        a = 0
        while a == 0:
            a = random.randrange(n)
        if not miller_rabin_pass(a, n):
            return False
    return True



def gcd(a, b):
    while b != 0:
	a, b = b, a%b
    return a 

def findfactor(n):
    for c in range(1, 50):
	x = y = random.randint(1, n-1)
	x = (x * x + c) % n
	y = (y * y + c) % n
	y = (y * y + c) % n
	while True:
	    t = gcd(n, abs(x-y))
	    if t == 1:
		x = (x * x + c) % n
		y = (y * y + c) % n
		y = (y * y + c) % n
	    elif t == n:
		break
	    else:
		return t
    raise FactorError("couldn't find a factor.")
	
def factor(n):
    r = []
    while True:
	if isprime(n):
	    r.append(n)
	    break
	try:
	    f = findfactor(n)
	    r.append(f)
	    n = n / f
	except FactorError, msg:
	    r.append(n)
	    break
    r.sort()
    return r 

def doit(n):
	flist = factor(n)
	print locale.format("%d", n, True), "="
	for f in flist:
		print "\t%s" % locale.format("%d", f, True)

locale.setlocale(locale.LC_ALL, "")

doit(2**98-1)

This is a fairly challenging factorization, and after a few seconds, it outputs:

316,912,650,057,057,350,374,175,801,343 =
	3
	43
	127
	4,363,953,127,297
	4,432,676,798,593

Comments

Comment from Phil
Time 7/1/2009 at 3:24 am

Thanks for mentioning my blog. Perhaps you could contribute your solution as a comment.

Phil

Comment from Zeke
Time 9/10/2009 at 3:54 pm

Thanks for this program. You clearly put some effort into it. I found so many silly programs on the web that did nothing better than divide by all the odd numbers below the sqrt of the number to be factored.

Comment from factoring software
Time 2/23/2010 at 8:19 am

I was looking some web materials regarding factoring software but this is not I was looking for. I was looking for something related to invoice management (also called factoring). However it’s good to see the old-friend Python programming langugage 🙂

Comment from Phillip
Time 10/15/2012 at 5:26 pm

The program doesnt work for me

Comment from Brian
Time 3/5/2016 at 3:18 am

Did not work first up. Tried some changes to allow for changes from Python 2 to 3 (e.g. print statements need ()). When run, obtained 3 and the large factor, immediately after ran again and obtained 43 and the large factor (no 3) ?? Again, got 129 and the large factor.
Gave up. I have only just started on Python, so some of the statements are a bit obscure. For example, why are there duplicate lines in the function find factor??