import math, fractions, operator class Toolbox(object): def egcd(self,a, b): if a == 0: return (b, 0, 1) else: g, y, x = self.egcd(b % a, a) return (g, x - (b // a) * y, y) def square_and_multiply(self, g, e, m): # g is the base, e is the exponent, m is the modulus. # We want to handle all integers e if e < 0: g = self.modinv(g) e = -e elif e == 0: return 1 # Now assume that e > 0. # Get binary representation of e, and note that the first two # symbols are 0b when e is positive, so we cut them away. be = bin(e)[2:] a = 1 for b in be: a = (a * a) % m if b == '1': a = (a * g) % m return a class Factoring(object): def __init__(self): self.tb = Toolbox() def pollard_p(self,n, B): print 'Running pollard_p on n = ' + str(n) a = 2 print 'Step 1: setting a = ' + str(a) print 'Step 2: for j from 2 to ' + str(B) + ':' for j in range(2,B): a = self.tb.square_and_multiply(a,j,n) print 'a <- a^'+str(j)+' = ' + str(a) + ' mod ' + str(n) d = fractions.gcd((a-1),n) print 'Gcd of a-1 and n is:' print 'gcd('+str(a)+'-1, '+str(n)+') = gcd('+str(a-1)+', '+str(n)+') = ' + str(d) if d > 1 and d < n: print 'Result of pollard_p is: ' +str(d) print 'n = ' + str(d) + '*' + str(n/d) else: print "Factoring failed" def pollard_rho_f(self,x,n): return (x**2 + 1)%n def pollard_rho(self,n = 3006611): print "Running pollard_rho on n = " + str(n) points = [] cycle = False x1 = 2 points.append(x1) print "x1 = " + str(x1) x2 = self.pollard_rho_f(x1,n) print "x2 = " + str(x2) p = fractions.gcd((x1-x2),n) print "Gcd(x1-x2,n) = " + str(p) it = 0 while p == 1: it += 1 x1 = self.pollard_rho_f(x1,n) if x1 in points and cycle == False: print "Cycle reached" cycle == True else: points.append(x1) x2 = self.pollard_rho_f(x2,n) x2 = self.pollard_rho_f(x2,n) p = fractions.gcd((x1-x2),n) print "Iteration number " + str(it) print "x1 = " + str(x1) print "x2 = " + str(x2) print "Gcd(x1-x2,n) = " + str(p) if p == n: print "Factoring failed" else: print "Factoring successful" print "n = " + str(p) + "*" + str((n/p)) print """ Usage: python -i factoring.py or: ./factoring.py (if you have set the executable flag) The file provides the class Factoring, which you can use by typing obj = Factoring() It contains the following methods: pollard_p(n,B): Runs the pollard p-1 algorithm on the number n using the bound B. pollard_rho(n): Runs the pollard rho algorithm on the number n. Example obj = Factoring() obj.pollard_p(3006611,12) obj.pollard_rho(3006611) """