Revision history [back]

Try the following code instead:

import time
p = 101135929216614342638630785939670479796699743028362954839791101900457831250749

A = -3
B =  1
F = GF(p)
E = EllipticCurve( F, [A,B] );

S.<W> = PolynomialRing( F )
K.<a> = GF( p^2, modulus=W^2+W+1 )
print "Modulus of K is =", K.modulus()                    

R.<z> = PolynomialRing( K, sparse=True )

x = (a + 2  )/3 * (z^p-a*z)
y = (1 + 2*a)/3 * (z^p-  z)

f = y^2 - ( x^3 + A*x + B )
# print "\n Elliptic Curve fE(z) = ", f

P = E.random_point()
Q = E.random_point()

print "point1 =", P.xy()
print "point2 =", Q.xy()

start1 = time.time()
H      = P + Q;
end1   = time.time()
Hx, Hy = H.xy()
print "H = P + Q has the components:\nHx = %s\nHy = %s" % ( Hx, Hy )
print "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 "g =", g

    f1 = ( f % g ).monic()
    print "f1 = gcd = ", f1

    f2 = ( z - P[0] - P[1]*a ) * ( z - Q[0] - Q[1]*a )
    print "\npoint equation =", f2

    f3 = f1 // f2
    print "f3 =", f3

    c = f3.constant_coefficient()
    M0, M1 = S(c).coefficients()

    G = E.point( ( -M0, M1 ) )
    end = time.time()

    Gx, Gy = G.xy()
    print "G = P + Q (?) has the components:\nGx = %s\nGy = %s" % ( Gx, Gy )
    print "Time for this operation (new approach): %s" % ( end - start )

Code is rewritten so that

• it is clean and readable (at least for me), and hopefully will no longer lead to errors,
• the reader has no overwhelming numbers combat to absolve,
• there is no redefinition of R, and of a, and a "dirty" isolation of coefficients related to a, and the polynomial ring R1 does not become a point after some lines of code,
• there is no hidden mathematical structure, for instance it is simple to see the formulas: $$x =\frac{a+2}3(z^p-az)\ ,$$ $$y =\frac{1+2a}3(z^p-z)\ ,$$ $$f=y^2-(x^3 +Ax+B)\ ,$$ so that the answerer can somehow "profit" from the invested work. (Why do you keep this information secret? Why do you not give a link, or a small comment for the "new addition formula"? Why do you use some fE and fL in the "private comments" and not explain what happens behind?)
• note: some code was left "as it was" to see where the new code was changed / inserted. Just omit the prints between setting start and end to get the net time used for the computations.

The sage interpreter (on this old linux machine) gives me (among other information from the numerous prints) this time the following:

Modulus of K is = x^2 + x + 1

H = P + Q has the components:
Hx = 70583706647472158282446068656049767531471554371674207909734012354515559580768
Hy = 1539735264843042217709244891894727788602955406703432172905441025552368530057
Time for this operation (existing approach): 0.000148057937622

G = P + Q (?) has the components:
Gx = 70583706647472158282446068656049767531471554371674207909734012354515559580768
Gy = 1539735264843042217709244891894727788602955406703432172905441025552368530057
Time for this operation (new approach): 0.00576591491699

P.S. Please give a link to the related mathematical construction used above, this would be after all a fair gentle nice touch.