def ECfactorAdd(Point1,Point2,Group):
    a = Group[0]
    b = Group[1]
    p = Group[2]
    #print Point2
    if Point1!=[]:
        x1 = Point1[0]
        y1 = Point1[1]
    if Point2!=[]:
        x2 = Point2[0]
        y2 = Point2[1]
    if ZZ(mod(4*a^3 + 27*b^2, p)) == 0:
        print "This is not an ellitpic curve"
    elif Point1!=[] and ZZ(mod(y1^2, p)) != ZZ(mod(x1^3 + a*x1 + b,p)):
        print "Point 1 is not on the elliptic curve."
    elif Point2!=[] and ZZ(mod(y2^2, p)) != ZZ(mod(x2^3 + a*x2 + b,p)):
        print "Point 2 is not on the elliptic curve."
    else:
        if Point1==[]:
            R=Point2
        elif Point2=={}:
            R=Point1
        else:
            if x1==x2 and 0==ZZ(mod(y1+y2,p)):
                R=[]
            elif x1==x2 and y1==y2:
                R=ECfactorDouble(Point1,Group)
                if R==True:
                    return(True)
            else:
                g=gcd(x1-x2,p)
                if (g>1):
                    print "factor is {0}".format(g)
                    return(True)
                s=ZZ(mod((y1-y2)/(x1-x2),p))
                x=ZZ(mod(s^2-(x1+x2),p))
                y=ZZ(mod(s*(x1-x)-y1,p))
                R=[x,y]
    return R

def ECfactorDouble(Point,Group):
    a = Group[0]
    b = Group[1]
    p = Group[2]
    if Point!=[]:
        x1 = Point[0]
        y1 = Point[1]
        if ZZ(mod(4*a^3 + 27*b^2, p)) == 0:
            print "This is not an ellitpic curve"
        elif Point!= [] and ZZ(mod(y1^2,p))!= ZZ(mod(x1^3+a*x1+b,p)):
            print "point to double not on elliptic curve"
        elif y1==0:
            R=[]
        else:
            g = gcd(y1,p)
            if g>1:
                print "Factor is {0}".format(g)
                return True
            s = ZZ(mod((3*x1^2+a)/(2*y1),p))
            x = ZZ(mod(s^2-(x1+x1),p))
            y = ZZ(mod(s*(x1-x)-y1,p))
            R = [x,y]
    else:
        R=[]
    return R

def ECfactorTimes(Point,scalar,Group):
    ECIDENTITY = []
    if Point==ECIDENTITY or scalar ==0:
        return ECIDENTITY
    else:
        m = scalar
        pt = Point
        x = ECIDENTITY
        for j in xrange(1,scalar+1):
            if m%2==0:
                m = m/2
            else:
                m=(m-1)/2
                #print "in this pt"
                #print pt
                x=ECfactorAdd(x,pt,Group)
                if x==True:
                    return true
            if m==0:
                return x
            pt = ECfactorDouble(pt,Group)
            #print "post double"
            #print pt
            if pt==True:
                return true

def ecfactor(Gp,pt,rounds):
    lpt = pt
    for j in xrange(1,rounds+1):
        #print "ECfactorTimes({0},{1},{2})".format(lpt,j,Gp)
        lpt = ECfactorTimes(lpt,j,Gp)
        #print "lpt {0}".format(lpt)
        if lpt ==True:
            return True
    #print "not enough rounds to discover factor"

p = next_prime(34627)
q = next_prime(434756)
n = p*q
size = 1000
r =[]
gg=[]
bb=[]
GG=[]
for j in xrange(size):
    r.append(ZZ.random_element(6, n))
    gg.append([r[j],1])
    a = ZZ.random_element(6,n)
    bb.append(ZZ(mod(1-a*r[j]-r[j]^3,n)))
    GG.append([a,bb[j],n])
for j in xrange(100):
    print "Working on group {0}".format(j)
    z = ecfactor(GG[j],gg[j],150)
    print z
    if z==True:
        break
    if j%50==49:
        print "50 tests without enough rounds"

p = next_prime(11489573485379837846709870987878868768789114324321423599019)
q = next_prime(2814211321173)
n = p*q
size = 1000
r =[]
gg=[]
bb=[]
GG=[]
for j in xrange(size):
    r.append(ZZ.random_element(664, n))
    gg.append([r[j],1])
    a = ZZ.random_element(n)
    bb.append(ZZ(mod(1-a*r[j]-r[j]^3,n)))
    GG.append([a,bb[j],n])

for j in xrange(size):
    #print "Working on group {0}".format(j)
    z = ecfactor(GG[j],gg[j],150)
    #print z
    if z==True:
        break
    if j%50==49:
        #this was changed so sage would complete the attack
        #to many outputs will kill the program
        print "50 tests without enough rounds"

#Example 3
p = next_prime(11111112131893798709870987878868768789114324321423599019)
q = next_prime(281421132117)
n = p*q
size = 1000
r =[]
gg=[]
bb=[]
GG=[]
for j in xrange(size):
    r.append(ZZ.random_element(664, n))
    gg.append([r[j],1])
    a = ZZ.random_element(n)
    bb.append(ZZ(mod(1-a*r[j]-r[j]^3,n)))
    GG.append([a,bb[j],n])

for j in xrange(size):
    #print "Working on group {0}".format(j)
    z = ecfactor(GG[j],gg[j],150)
    #print z
    if z==True:
        break

# Encrypting in the group Gp, with pt being the message to be encrypted, and e the encryption exponent.
def RSAEncrypt(Group,Point,e):
    ECIDENTITY = []
    if Point == ECIDENTITY or e ==0:
        return ECIDENTITY
    else:
        m = e
        pt = Point
        x = ECIDENTITY
        for j in xrange(1,e+1):
            if m%2==0:
                m = m/2
            else:
                m=(m-1)/2
                #print "in this pt"
                #print pt
                x=ECfactorAdd(x,pt,Group)
                if x==True:
                    return true
            if m==0:
                return x
            pt = ECfactorDouble(pt,Group)
            #print "post double"
            #print pt
            if pt==True:
                return true

p = next_prime(111111121318937) #9879870987878868768789114324321423599019)
q = next_prime(281421132117)
print(p % 3)
print(q % 3)
N = p*q
print(N)
O = lcm(p+1,q+1)
print(O)
#
# Suppose message is
M = 123145
a = 0
b = (1 - M^3) % N
Gp = [a,b,N]
pt = [M,1]
e  = 11
d = 1/e % O
print(d)
D = gcd(e,O)
print(D)
NN = RSAEncrypt(Gp,pt,e)
print(NN)

M = 5321528147665414786701520   #149040454574391513491803468739254610223175457545379061985977134807
S = 4675466774218418470833385   #587032741548116016273841645840975660731740571414562228535877822
A = 0
L=S^2-M^3
X=L % N #98327432987493874
print(X)
#B =(S^2-M^3) % N
#ZZ(mod(S^2-M^3,N))
#(S^2 - M^3) % N #% N #(S^2 - M^3) % N
#print(B)
# (S^2 - M^3)
#4675466774218418470833385*2 - 5321528147665414786701520
#GP = [A,B,N]
#Pt = [M,S]

#Z = RSAEncrypt(GP,Pt,d)
#print(Z)










# N = p*q is RSA modulus
# Message --> ASCIIPAD = M --> [M,1]
# Curve y^2 = x^3 + b where
# b = (1-M^3) mod N
# Group order is (p+1)*(q+1)
# Encr Exp is e where gcd(e,Group order) = 1.

p=next_prime(378468376837)
q=next_prime(3784283748327468)
n=p*q
NA=(p+1)*(q+1)
m1=38957435734
b = (1-m1^3) % n
G=[0,b,n]
ECfactorTimes([m1,1],457384,G)

4^11