Elliptic Curve arithmetic.

edit

The following algorithm for point addition for elliptic curve arithmetic on 10 digit prime number and it gave me proper result in sage.

import time
p=3628273133
start = time.time()
E = EllipticCurve(GF(p),[0,0,0,2,7]); E
P = E.random_point();# P                            # select Random point P on elliptic Curve      
Q = E.random_point(); # Q 
print"Point1 = ",P                               # print point P 
print"Point2 = ",Q 
R1=P+Q                           #existing Point addition Approach 
print("the time taken for the existing approach is given by ", end - start) #time for existing approach

the following result is obtained

Elliptic Curve defined by y^2 = x^3 + 2*x + 7 over Finite Field of size 3628273133
Point1 =  (1725499584 : 3508204967 : 1)
Point2 =  (1305216092 : 2568225818 : 1)

 Addition of two points Existing Approach (P+Q) = (445288498 : 1892712465 : 1)
('the time taken for the existing approach is given by ', 0.007417201995849609)

I have implemented the new algorithm for point addition and point doubling based on tool Trace. so that it will transform x and y variable into z.(one variable approach). But it will work only 4 digit prime number that is only 16 bit. But for cryptographic application we required 160 bit or 120 bit. what are the changes required in my algorithm.

import time
start = time.time()
p =5          #Defining the prime field
k.<a> = FiniteField (p^2) ; k where *a* represent theta
R.<z> = PolynomialRing(k); R                                      #Defining extension of P

n1=k(1).trace()                                           #Finding trace of 1
#print ("trace(1)=", n1)
n2=k(a).trace()                                           #Finding trace of 'theta'
#print ("trace(a)=", n2)
n3=k(a^2).trace()                                         #Finding trace of 'theta^2'
#print ("trace(a^2)=", n3)
B1,B2,B3,B4,a1,b1,a2,b2 = var('B1,B2,B3,B4,a1,b1,a2,b2')
B1 = (n1*a1 + n2*b1)                                      #Finding trace of 'beta1'
print ("trace(B1)=", B1)
B2 = (n2*a1 + n3*b1)                                      #Finding trace of 'beta1*theta'
print ("trace(B1*a)=", B2)
B3 = (n1*a2 + n2*b2)                                      #Finding trace of 'beta2'
print ("trace(B2)=", B3)
B4 = (n2*a2 + n3*b2)                                      #Finding trace of 'beta2*theta'
print ("trace(B2*a)=", B4)
A=matrix(k,[[n1,n2], [n2,n3]]); B=vector(k,[1,0]); A_B=A.augment(B, subdivide=True);#A
A_B.echelonize();#A_B

a1 = A_B[0,2]                                             #Finding value of 'a1'
#print ("a1 =", a1)
b1 = A_B[1,2]                                             #Finding value of 'b1'
#print ("b1 =", b1)
C1 = a1 + b1*a
#print ("Thus we have B1 = ", C1)
C=matrix(k,[[n1,n2], [n2,n3]]); D=vector(k,[0,1]); C_D=C.augment(D, subdivide=True)
C_D.echelonize()
a2 = C_D[0,2]                                             #Finding value of 'a2'
#print ("a2 =", a2)
b2 = C_D[1,2]                                             #Finding value of 'b2'
#print ("b2 =", b2)
C2 = a2 + b2*a
#print ("Thus we have B2 = ", C2)
C11 = k(a1 + b1*a)                        #Hence defining beta1 in terms of a1,b1 and theta
C12 = k(a2 + b2*a)                        #Hence defining beta2 in terms of a2,b2 and theta
x = C11*z + (C11*z)^p                     #Finding value of x in terms of z and theta
print ("x =", x)
y = C12*z + (C12*z)^p                     #Finding value of y in terms of z and theta
print ("y =", y)

the above algorithm generate the value of x and y in terms of z. but the limitation is only for small prime numbers.