Contact
CoCalc Logo Icon
StoreFeaturesDocsShareSupport News Sign UpSign In
| Download
Views: 140
def add_affine(P,Q,A): """addition algorithm for affine points an elliptic curve in short Weierstrass form -- handles all cases (including point at infinity)""" if P == O: return Q if Q == O: return P x1=P[0]; y1=P[1]; x2=Q[0]; y2=Q[1]; if x1 != x2: m = (y2-y1)/(x2-x1) # usual case: P and Q are distinct and not opposites else: if y1 == -y2: return O # P = -Q (includes case where P=Q is 2-torsion) m = (3*x1^2+A) / (2*y1) # P = Q so we are doubling x3 = m^2-x1-x2 y3 = m*(x1-x3)-y1 return (x3,y3,1) def negate(P): """negates the point P on an elliptic curve in short Weierstrass form""" if P == O: return O return (P[0],-P[1],P[2]) def dbl_affine(P,A): """doubles an affine non-2-torsion point on an elliptic curve in short Weierstrass form""" x1 = P[0]; y1 = P[1] m = (3*x1^2+A) / (2*y1) x3 = m^2-2*x1 y3 = m*(x1-x3)-y1 return (x3,y3,1) def random_point(A,B): """generates a random affine point on the elliptic curve y^2 = x^2 + Ax + B""" F=A.parent() x0=F.random_element(); t=(x0^3+A*x0+B) while not t.is_square(): x0=F.random_element(); t=(x0^3+A*x0+B) return (x0,sqrt(t),1)
p=random_prime(2^512,lbound=2^511) F=GF(p) A=F(3); B=F.random_element() P0=random_point(A,B) Q0=random_point(A,B) print "starting tests" timeit('add_affine(P0,Q0,A)',number=50000) timeit('add_affine(P0,P0,A)',number=50000) timeit('dbl_affine(P0,A)',number=50000)
starting tests 50000 loops, best of 3: 13.4 µs per loop 50000 loops, best of 3: 16.4 µs per loop 50000 loops, best of 3: 15.7 µs per loop
def add_edwards(P,Q,d): """adds two projective points on an elliptic curve in Edwards form (assumes d non-square, so operation is complete)""" # uses unoptimized formula derived in class (could save 1M with optimization) x1=P[0]; y1=P[1]; z1=P[2]; x2=Q[0]; y2=Q[1]; z2=Q[2] x1y2 = x1*y2; x2y1 = x2*y1 r = z1*z2; rr = r^2; s = x1y2+x2y1; t = d*x1y2*x2y1; u = y1*y2 - x1*x2 v = rr+t; w = rr-t x3 = r*s*w y3 = r*u*v z3 = v*w return (x3,y3,z3) def dbl_edwards(P): """doubles a projective point on an elliptic curve in Edwards form""" # uses optimized formula from Bernstein-Lange x1 = P[0]; y1 = P[1]; z1 = P[2] B=(x1+y1)^2; C=x1^2; D=y1^2; E = C+D; J = E-2*z1^2; x3 = (B-E)*J; y3 = E*(C-D); z3 = E*J return (x3,y3,z3) def neg_edwards(P): return (-P[0],P[1],P[2]) def random_edwards_point(d): """generates a random projective point on the Edwards curve x^2 + y^2 = 1+d*x^2*y^2 (assumes d non-square)""" F=d.parent() x0=F.random_element(); t=(1-x0^2)/(1-d*x0^2) while not t.is_square(): x0=F.random_element(); t=(1-x0^2)/(1-d*x0^2) return (x0,sqrt(t),1) def on_edwards_curve (P,d): x0=P[0]; y0=P[1]; z0=P[2] return z0^2*(x0^2+y0^2) == z0^4 + d*x0^2*y0^2 def is_id_edwards (P): if P[0] == 0 and P[1] == P[2]: return true else: return false
p = 17 F=GF(p) d = F.multiplicative_generator() print "Points on Edwards curve x^2 + y^2 = 1 + %dx^2y^2 over F_%d"%(d,p) for a in F: for b in F: if on_edwards_curve([a,b,1],d): print [a,b]
Points on Edwards curve x^2 + y^2 = 1 + 3x^2y^2 over F_17 [0, 1] [0, 16] [1, 0] [2, 5] [2, 12] [3, 4] [3, 13] [4, 3] [4, 14] [5, 2] [5, 15] [7, 7] [7, 10] [10, 7] [10, 10] [12, 2] [12, 15] [13, 3] [13, 14] [14, 4] [14, 13] [15, 5] [15, 12] [16, 0]
p=random_prime(2^512,lbound=2^511) F=GF(p) d=F(-1); while d.is_square(): d-=1; P0=random_edwards_point(d) Q0=random_edwards_point(d) print "starting tests" timeit('add_edwards(P0,Q0,d)',number=50000) timeit('add_edwards(P0,P0,d)',number=50000) timeit('dbl_edwards(P0)',number=50000)
starting tests 50000 loops, best of 3: 13.1 µs per loop 50000 loops, best of 3: 14.4 µs per loop 50000 loops, best of 3: 10.3 µs per loop