Welcome, guest | Sign In | My Account | Store | Cart

This code is implementation of Pollard Rho prime factorization. As i am a bit new in python so further improvement is appreciated.Also added Brent variant.

Python, 108 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108``` ```# To change this template, choose Tools | Templates # and open the template in the editor. __author__="Mukesh Tiwari" __date__ ="\$Feb 10, 2010 1:35:26 AM\$" import random from Queue import Queue def gcd(a,b): while b: a,b=b,a%b return a def rabin_miller(p): if(p<2): return False if(p!=2 and p%2==0): return False s=p-1 while(s%2==0): s>>=1 for i in xrange(10): a=random.randrange(p-1)+1 temp=s mod=pow(a,temp,p) while(temp!=p-1 and mod!=1 and mod!=p-1): mod=(mod*mod)%p temp=temp*2 if(mod!=p-1 and temp%2==0): return False return True def brent(n): if(n%2==0): return 2; x,c,m=random.randrange(0,n),random.randrange(1,n),random.randrange(1,n) y,r,q=x,1,1 g,ys=0,0 while(True): x=y for i in range(r): y,k=(y*y+c)%n,0 while(True): ys=y for i in range(min(m,r-k)): y,q=(y*y+c)%n,q*abs(x-y)%n g,k=gcd(q,n),k+m if(k>= r or g>1):break r=2*r if(g>1):break if(g==n): while(True): ys,g=(x*x+c)%n,gcd(abs(x-ys),n) if(g>1):break return g def pollard(n): if(n%2==0): return 2; x=random.randrange(2,1000000) c=random.randrange(2,1000000) y=x d=1 while(d==1): x=(x*x+c)%n y=(y*y+c)%n y=(y*y+c)%n d=gcd(x-y,n) if(d==n): break; return d; def factor(n): #if(rabin_miller(n)): # print n # return #d=pollard(n) #if(d!=n): # factor(d) # factor(n/d) #else: # factor(n) Q_1=Queue() Q_2=[] Q_1.put(n) while(not Q_1.empty()): l=Q_1.get() if(rabin_miller(l)): Q_2.append(l) continue d=pollard(l) if(d==l):Q_1.put(l) else: Q_1.put(d) Q_1.put(l/d) return Q_2 if __name__ == "__main__": while(True): n=input(); L=factor(n) L.sort() i=0 while(i
 Created by Mukesh Tiwari on Tue, 9 Feb 2010 (MIT)