Elliptic Curve arithmetic.

asked 2017-07-31 04:52:26 -0500

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

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
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

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)
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.

edit retag flag offensive close merge delete


Please give us a mathematical reference of the used algorithm. It is hard to understand what happens without a working example. The setting B1,B2,B3,B4,a1,b1,a2,b2 = var('B1,B2,B3,B4,a1,b1,a2,b2') is not making too much sense for the B-variables, when we redefine them in the next lines. So it is hard to extract from the above if the a1,a2,b1,b2 should be used as variables, or arguments of a function, or will become explicit and the above lines are just pseudocode.

Also note that z is transcendental, the symbol / variable of a polynomial ring. Then in the last lines we use its $p$-power. (For a to-be-big $p$.) And then the code is abruptly terminated.

dan_fulea gravatar imagedan_fulea ( 2017-08-01 17:19:53 -0500 )edit