2862
Comment:

← Revision 5 as of 20081114 13:42:05 ⇥
2883
converted to 1.6 markup

Deletions are marked like this.  Additions are marked like this. 
Line 82:  Line 82: 
== Third Formula == 
Edwards coordinates formulas.
See email to sagedays6, along with http://hyperelliptic.org/EFD/edwards.html
Paul Zimmerman is working on this
First Formula
%time R.<y1,y2,c,d,x1,x2> = QQ[] e = 1d*c^4 S = R.quotient([x1^2+y1^2c^2*(1+d*x1^2*y1^2), x2^2+y2^2c^2*(1+d*x2^2*y2^2)]) # the Edwards addition law: x3 = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)) y3 = (y1*y2x1*x2)/(c*(1d*x1*x2*y1*y2)) # map to the Montgomery curve: u1 = (c+y1)/(cy1); v1=2*c*u1/x1 g = (1/e)*v1^2u1^3(4/e2)*u1^2u1 print S(g.numerator()) u2 = (c+y2)/(cy2); v2 = 2*c*u2/x2 g = (1/e)*v2^2u2^3(4/e2)*u2^2u2 print S(g.numerator()) u3 =(c+y3)/(cy3); v3=2*c*u3/x3 g = (1/e)*v3^2u3^3(4/e2)*u3^2u3 print S(g.numerator()) # add on the Montgomery curve: lambd = (v2v1)/(u2u1) r3 = (1/e)*lambd^2(4/e2)u1u2; s3 =lambd*(u1r3)v1; # check the answer: print S((u3r3).numerator()), S((v3s3).numerator()) /// 0 0 0 0 0 CPU time: 0.06 s, Wall time: 0.09 s
Second Formula
#Here is the SAGE code corresponding to the 2nd version of the #addition. #Paul # 2007 Bernstein/Lange, 10M + 1S + 1C + 1D + 7add, # strongly unified: R.<c,d,X1,Y1,X2,Y2,Z1,Z2> = QQ[] e = 1d*c^4; S = R.quotient([(X1^2+Y1^2)*Z1^2c^2*(Z1^4+d*X1^2*Y1^2), (X2^2+Y2^2)*Z2^2c^2*(Z2^4+d*X2^2*Y2^2)]) x1 = X1/Z1; y1 = Y1/Z1; x2 = X2/Z2; y2 = Y2/Z2; x3 = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)); y3 = (y1*y2x1*x2)/(c*(1d*x1*x2*y1*y2)); # here are the formulas: A = Z1*Z2; B = A^2; C = X1*X2; D = Y1*Y2; E = d*C*D; F = BE; G = B+E; X3 = A*F*((X1+Y1)*(X2+Y2)CD); Y3 = A*G*(DC); Z3 = c*F*G; # check we get 0 print x3X3/Z3 print y3Y3/Z3
Third Formula
Here is another example, which was more tricky. David helped me. We had to use NumberField because QuotientRing did not work (unless I did a mistake).
Paul
# 2007 Bernstein/Lange, # 10M + 1S + 1C + 1D + 9add + 3timesi + 2times2, # strongly unified: # thanks to David Roe <[email protected]> for the help Gauss.<i> = NumberField(x^2+1) R.<c,d,X1,Y1,X2,Y2,Z1,Z2> = Gauss[] e = 1d*c^4 S = R.quotient([(X1^2+Y1^2)*Z1^2c^2*(Z1^4+d*X1^2*Y1^2), (X2^2+Y2^2)*Z2^2c^2*(Z2^4+d*X2^2*Y2^2)]) x1 = X1/Z1; y1 = Y1/Z1 x2 = X2/Z2; y2 = Y2/Z2 x3 = (x1*y2+y1*x2)/(c*(1+d*x1*x2*y1*y2)) y3 = (y1*y2x1*x2)/(c*(1d*x1*x2*y1*y2)) # here are the formulas: iX2 = i*X2; C2 = Y2+iX2; D2 = Y2iX2; iX1 = i*X1; C1 = Y1+iX1; D1 = Y1iX1; A = Z1*Z2; B = 2*A^2; C = C1*C2; D = D1*D2; L = D+C; M = Y1*Y2; N = 2*ML; E = d*M*N; F = BE; G = B+E; X3 = i*A*F*(DC); Y3 = A*G*L; Z3 = c*G*F; # check both are zero print x3X3/Z3 print y3Y3/Z3