14.01.2011, 21:52, "mukesh tiwari" <mukeshtiwari.ii...@gmail.com>: > Hello all , I have implemented Elliptic curve prime factorisation > using wikipedia [ > http://en.wikipedia.org/wiki/Lenstra_elliptic_curve_factorization]. > I think that this code is not optimised and posting for further > improvement. Feel free to comment and if you have any link regarding > Elliptic curve prime factorisation , kindly post it. > Thank you > > import math > import random > > #y^2=x^3+ax+b mod n > > def extended_gcd(a,b): # taken from wikipedia > x,y,lastx,lasty=0,1,1,0 > while b!=0: > q=a/b > a,b=b,a%b > x,lastx=(lastx-q*x,x) > y,lasty=(lasty-q*y,y) > if a<0: > return (-a,-lastx,-lasty) > else: > return (a,lastx,lasty) > def gcd(a,b): > if a < 0: a = -a > if b < 0: b = -b > if a == 0: return b > if b == 0: return a > while b != 0: > (a, b) = (b, a%b) > return a > > def randomCurve(N): > A,u,v=random.randrange(N),random.randrange(N),random.randrange(N) > B=(v*v-u*u*u-A*u)%N > return [(A,B,N),(u,v)] > > def addPoint(E,p_1,p_2): > if p_1=="Identity": return [p_2,1] > if p_2=="Identity": return [p_1,1] > a,b,n=E > (x_1,y_1)=p_1 > (x_2,y_2)=p_2 > x_1%=n > y_1%=n > x_2%=n > y_2%=n > if x_1 != x_2 : > d,u,v=extended_gcd(x_1-x_2,n) > s=((y_1-y_2)*u)%n > x_3=(s*s-x_1-x_2)%n > y_3=(-y_1-s*(x_3-x_1))%n > else: > if (y_1+y_2)%n==0:return ["Identity",1] > else: > d,u,v=extended_gcd(2*y_1,n) > s=((3*x_1*x_1+a)*u)%n > x_3=(s*s-2*x_1)%n > y_3=(-y_1-s*(x_3-x_1))%n > > return [(x_3,y_3),d] > > def mulPoint(E,P,m): > Ret="Identity" > d=1 > while m!=0: > if m%2!=0: Ret,d=addPoint(E,Ret,P) > if d!=1 : return [Ret,d] # as soon as i got anything > otherthan 1 > return > P,d=addPoint(E,P,P) > if d!=1 : return [Ret,d] > m>>=1 > return [Ret,d] > > def ellipticFactor(N,m,times=5): > for i in xrange(times): > E,P=randomCurve(N); > Q,d=mulPoint(E,P,m) > if d!=1 : return d > return N > > if __name__=="__main__": > n=input() > m=int(math.factorial(1000)) > while n!=1: > k=ellipticFactor(n,m) > n/=k > print k > > -- > http://mail.python.org/mailman/listinfo/python-list
Well, first of all you should read and follow this http://www.python.org/dev/peps/pep-0008/ :-) -- jabber: k...@ya.ru -- http://mail.python.org/mailman/listinfo/python-list
