I suspect the world would be better if that percentage were even greater.
A Simple Python Program for Factoring…
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 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??
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