i have implemented point addition and point doubling algorithm over elliptic curve. i want to use same algorithm for scalar multiplication i am unable to generate code for the same please guide. Both the sage math codes are given here.
point Addition
import time p =71 A=41 B=18 print"\n p=",p print"\n A=",A print"\n B=",B
F = GF(p) E = EllipticCurve( F, [A,B] );
S. = PolynomialRing( F ) K. = GF( p^2);#K.modulus#, modulus=W^2+W+1 ) print "\n Modulus of K is =", K.modulus()
R.<z> = PolynomialRing( K, sparse=True )
x= (65a + 42)z^71 + (6a + 30)z
y= (6a + 65)z^71 + (65a + 6)z
f=(22a + 9)z^213 + (23a + 52)z^143 + 68z^142 + (48a + 27)z^73 + 6z^72 + (33a + 53)z^71 + (49a + 53)z^3 + 68z^2 + (38a + 48)*z + 53
print "\n Elliptic Curve fE(z) = ", f
P = E.random_point() Q = E.random_point()
print "\n point1 =", P.xy() print "\n point2 =", Q.xy()
start1 = time.time() H = P + Q; end1 = time.time() Hx, Hy = H.xy() print "\n H = P + Q has the components:\nHx = %s\nHy = %s" % ( Hx, Hy ) print "\n Time for this operation (existing approach): %s" % ( end1 - start1 )
if P[0] != Q[0] : start = time.time()
g = ( + ( Q[0] - P[0] ) * y
- ( Q[1] - P[1] ) * x
- ( P[1]*Q[0] - Q[1]*P[0] ) )
print "\n Line equation =", g
f1 = ( f % g ).monic()
print "\n f1 = gcd (fE,fL) = ", f1
f2 = ( z - P[0] - P[1]*a ) * ( z - Q[0] - Q[1]*a )
print "\n point equation =", f2
f3 = f1 // f2
print "\n Division of two polynomials f1 & f2 =", f3
c = f3.constant_coefficient()
M0, M1 = S(c).coefficients()
G = E.point( ( -M0, M1 ) )
end = time.time()
Gx, Gy = G.xy()
print "\n G = P + Q has the components:\nGx = %s\nGy = %s" % ( Gx, Gy )
print "\n Time for this operation (new approach): %s" % ( end - start )
point Doubling
import time p =71 A=41 B=18 print"\n p=",p print"\n A=",A print"\n B=",B
F = GF(p) E = EllipticCurve( F, [A,B] );
S. = PolynomialRing( F ) K. = GF( p^2);#K.modulus#, modulus=W^2+W+1 ) print "\n Modulus of K is =", K.modulus()
R.<z> = PolynomialRing( K, sparse=True )
x= (65a + 42)z^71 + (6a + 30)z
y= (6a + 65)z^71 + (65a + 6)z
f=(22a + 9)z^213 + (23a + 52)z^143 + 68z^142 + (48a + 27)z^73 + 6z^72 + (33a + 53)z^71 + (49a + 53)z^3 + 68z^2 + (38a + 48)*z + 53
print "\n Elliptic Curve fE(z) = ", f
P = E(63,32)#.random_point()
Q = E.random_point()
print "\n point1 =", P.xy()
print "\n point2 =", Q.xy()
start1 = time.time() H = 2*P; end1 = time.time() Hx, Hy = H.xy() print "\n H = P + Q has the components:\nHx = %s\nHy = %s" % ( Hx, Hy ) print "\n Time for this operation (existing approach): %s" % ( end1 - start1 )
start = time.time()
g = ( ( 2 * P[1] * y ) - ( ( 3 * P[0]^2) + A ) * x -(-P[0]^3 + ( A * P[0] ) + 2 * B) ) print "\n Line equation =", g
f1 = ( f % g ).monic() print "\n f1 = gcd (fE,fL) = ", f1
f2 = ( z - P[0] - P[1]a )( z - P[0] - P[1]*a ) print "\n point equation =", f2
f3 = f1 // f2 print "\n Division of two polynomials f1 & f2 =", f3
c = f3.constant_coefficient() f4=(-c) M0, M1 = S(f4).coefficients();M0,M1
G = E.point( ( M0, -M1 ) ) end = time.time()
Gx, Gy = G.xy() print "\n G = P + Q has the components:\nGx = %s\nGy = %s" % ( Gx, Gy ) print "\n Time for this operation (new approach): %s" % ( end - start )
