Elliptic Curve Prime factorisation

[kost BebiX]

14.01.2011, 21:52, "mukesh tiwari" <mukeshtiwari.iiitm at 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.bx at ya.ru