Welcome, guest | Sign In | My Account | Store | Cart
```import math
import random

#y^2=x^3+ax+b mod n

def extended_gcd(a,b):
if a == 0 and b == 0: return (0, 0, 1)
if a == 0: return (abs(b), 0, b/abs(b))
if b == 0: return (abs(a), a/abs(a), 0)
x_sign = 1; y_sign = 1
if a < 0: a = -a; x_sign = -1
if b < 0: b = -b; y_sign = -1
x = 1; y = 0; r = 0; s = 1
while b != 0:
(c, q) = (a%b, a/b)
(a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
return (a, x*x_sign, y*y_sign )

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)
C=(v*v-u*u*u-A*u)%N
return [(A,C,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()
while n!=1:
k=ellipticFactor(n,int(math.factorial(1000)))
n/=k
print k
```