Affine negation formulas: -(x1,y1)=(x1,-y1).
The neutral element of the curve is the unique point at infinity, namely (0:1:0) in projective coordinates.
Jacobian coordinates with a4=0 for short Weierstrass curves
name Jacobian coordinates with a4=0
assume a = 0
variable X
variable Y
variable Z
satisfying x = X/Z^2
satisfying y = Y/Z^3
用最小2乘法时最佳组合:
Smallest multiplication counts assuming I=100M, S=1M, *param=0M, add=0M, *const=0M:
16M for addition: 11M+5S. 12M+4S. 12M+4S. 12M+4S.
11M for addition with Z2=1: 7M+4S. 8M+3S. 8M+3S. 8M+3S.
7M for addition with Z1=Z2: 5M+2S.
6M for addition with Z1=1 and Z2=1: 4M+2S.
14M for readdition: 10M+4S after 11M+5S. 11M+3S after 12M+4S. 11M+3S after 12M+4S. 11M+3S after 12M+4S.
11M for readdition with Z2=1: 7M+4S after 7M+4S. 8M+3S after 8M+3S. 8M+3S after 8M+3S. 8M+3S after 8M+3S.
7M for readdition with Z1=Z2: 5M+2S after 5M+2S.
6M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
7M for doubling: 2M+5S.
6M for doubling with Z1=1: 1M+5S.
15M for tripling: 5M+10S. 8M+7S.
104M for scaling: 1I+3M+1S.
Smallest multiplication counts assuming I=100M, S=0.8M, *param=0M, add=0M, *const=0M:
15M for addition: 11M+5S.
10.2M for addition with Z2=1: 7M+4S.
6.6M for addition with Z1=Z2: 5M+2S.
5.6M for addition with Z1=1 and Z2=1: 4M+2S.
13.2M for readdition: 10M+4S after 11M+5S.
10.2M for readdition with Z2=1: 7M+4S after 7M+4S.
6.6M for readdition with Z1=Z2: 5M+2S after 5M+2S.
5.6M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
6M for doubling: 2M+5S.
5M for doubling with Z1=1: 1M+5S. 13M for tripling: 5M+10S.
103.8M for scaling: 1I+3M+1S.
Smallest multiplication counts assuming I=100M, S=0.67M, *param=0M, add=0M, *const=0M:
14.35M for addition: 11M+5S.
9.68M for addition with Z2=1: 7M+4S.
6.34M for addition with Z1=Z2: 5M+2S.
5.34M for addition with Z1=1 and Z2=1: 4M+2S.
12.68M for readdition: 10M+4S after 11M+5S.
9.68M for readdition with Z2=1: 7M+4S after 7M+4S.
6.34M for readdition with Z1=Z2: 5M+2S after 5M+2S.
5.34M for readdition with Z1=1 and Z2=1: 4M+2S after 4M+2S.
5.35M for doubling: 2M+5S.
4.35M for doubling with Z1=1: 1M+5S.
11.7M for tripling: 5M+10S.
103.67M for scaling: 1I+3M+1S.
挑一个用SAGE运行如下:
Assumptions: Z1=1.
Cost: 1M + 5S + 7add + 1*8 + 3*2 + 1*3.
Source: 2007 Bernstein–Lange.
Explicit formulas:
XX = X1^2
YY = Y1^2
YYYY = YY^2
S = 2*((X1+YY)^2-XX-YYYY)
M = 3*XX+a
T = M^2-2*S
X3 = T
Y3 = M*(S-T)-8*YYYY
Z3 = 2*Y1
def mynumerator(x):
if parent(x) == R:
return x
return numerator(x)
class fastfrac:
def __init__(self,top,bot=1):
if parent(top) == ZZ or parent(top) == R:
self.top = R(top)
self.bot = R(bot)
elif top.__class__ == fastfrac:
self.top = top.top
self.bot = top.bot * bot
else:
self.top = R(numerator(top))
self.bot = R(denominator(top)) * bot
def reduce(self):
return fastfrac(self.top / self.bot)
def sreduce(self):
return fastfrac(I.reduce(self.top),I.reduce(self.bot))
def iszero(self):
return self.top in I and not (self.bot in I)
def isdoublingzero(self):
return self.top in J and not (self.bot in J)
def __add__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top + self.bot * other,self.bot)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.bot + self.bot * other.top,self.bot * other.bot)
return NotImplemented
def __sub__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top - self.bot * other,self.bot)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.bot - self.bot * other.top,self.bot * other.bot)
return NotImplemented
def __neg__(self):
return fastfrac(-self.top,self.bot)
def __mul__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top * other,self.bot)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.top,self.bot * other.bot)
return NotImplemented
def __rmul__(self,other):
return self.__mul__(other)
def __div__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top,self.bot * other)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.bot,self.bot * other.top)
return NotImplemented
def __pow__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top ^ other,self.bot ^ other)
return NotImplemented
x^2+y^2=c^2*(1+d*x^2*y^2)是超奇异的,不算EC,但特点是 point (0,c). The point (0,-c) has order 2. The points (c,0) and (-c,0) have order 4.
如用仿射座标:
x=Z/X
y=Z/Y
Smallest multiplication counts assuming I=100M, S=1M, *param=0M, add=0M, *const=0M:
10M for addition: 9M+1S.
9M for addition with Z2=1: 8M+1S. 9M.
9M for addition with X2=1: 8M+1S.
7M for addition with Z1=1 and Z2=1: 7M.
10M for readdition: 9M+1S after 9M+1S.
9M for readdition with Z2=1: 8M+1S after 8M+1S. 9M after 9M.
9M for readdition with X2=1: 8M+1S after 8M+1S.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
7M for doubling: 3M+4S.
6M for doubling with Z1=1: 3M+3S.
13M for tripling: 9M+4S.
102M for scaling: 1I+2M.
Smallest multiplication counts assuming I=100M, S=0.8M, *param=0M, add=0M, *const=0M:
9.8M for addition: 9M+1S.
8.8M for addition with Z2=1: 8M+1S.
8.8M for addition with X2=1: 8M+1S.
7M for addition with Z1=1 and Z2=1: 7M.
9.8M for readdition: 9M+1S after 9M+1S.
8.8M for readdition with Z2=1: 8M+1S after 8M+1S.
8.8M for readdition with X2=1: 8M+1S after 8M+1S.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
6.2M for doubling: 3M+4S.
5.4M for doubling with Z1=1: 3M+3S.
12.2M for tripling: 9M+4S.
102M for scaling: 1I+2M.
Smallest multiplication counts assuming I=100M, S=0.67M, *param=0M, add=0M, *const=0M:
9.67M for addition: 9M+1S.
8.67M for addition with Z2=1: 8M+1S.
8.67M for addition with X2=1: 8M+1S.
7M for addition with Z1=1 and Z2=1: 7M.
9.67M for readdition: 9M+1S after 9M+1S.
8.67M for readdition with Z2=1: 8M+1S after 8M+1S.
8.67M for readdition with X2=1: 8M+1S after 8M+1S.
7M for readdition with Z1=1 and Z2=1: 7M after 7M.
5.68M for doubling: 3M+4S.
5.01M for doubling with Z1=1: 3M+3S. 11.68M for tripling: 9M+4S.
102M for scaling: 1I+2M.
挑一个5.01M for doubling with Z1=1: 3M+3SCost: 9M + 4S + 1*c + 1*d + 7add + 1*4 + 1*2.
Source: 2007 Bernstein–Lange.
Explicit formulas:
XX = X1^2
YY = Y1^2
ZZ = (c*Z1)^2
D = XX+YY
DD = D^2
E = 4*(D-d*ZZ)
H = 2*D*(YY-XX)
P = DD-XX*E
Q = DD-YY*E
X3 = (H+Q)*Q*X1
Y3 = (H-P)*P*Y1
Z3 = P*Q*Z1
SAGE运行:
def mynumerator(x):
if parent(x) == R:
return x
return numerator(x)
class fastfrac:
def __init__(self,top,bot=1):
if parent(top) == ZZ or parent(top) == R:
self.top = R(top)
self.bot = R(bot)
elif top.__class__ == fastfrac:
self.top = top.top
self.bot = top.bot * bot
else:
self.top = R(numerator(top))
self.bot = R(denominator(top)) * bot
def reduce(self):
return fastfrac(self.top / self.bot)
def sreduce(self):
return fastfrac(I.reduce(self.top),I.reduce(self.bot))
def iszero(self):
return self.top in I and not (self.bot in I)
def isdoublingzero(self):
return self.top in J and not (self.bot in J)
def __add__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top + self.bot * other,self.bot)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.bot + self.bot * other.top,self.bot * other.bot)
return NotImplemented
def __sub__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top - self.bot * other,self.bot)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.bot - self.bot * other.top,self.bot * other.bot)
return NotImplemented
def __neg__(self):
return fastfrac(-self.top,self.bot)
def __mul__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top * other,self.bot)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.top,self.bot * other.bot)
return NotImplemented
def __rmul__(self,other):
return self.__mul__(other)
def __div__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top,self.bot * other)
if other.__class__ == fastfrac:
return fastfrac(self.top * other.bot,self.bot * other.top)
return NotImplemented
def __pow__(self,other):
if parent(other) == ZZ:
return fastfrac(self.top ^ other,self.bot ^ other)
return NotImplemented
uR = ((uw2*uw3))
uS = ((uR^2))
uT = ((uR*(fastfrac(1)+uw2+uw3)+uS))
uw5 = ((uT/(ud1+uT+ud2overd1plus1*uS)+uw1))
uA = ((uw2^2))
uJ = ((uA^2))
uK = ((uA+uJ))
uw4 = ((uK/(ud1+uK+ud2overd1plus1*uJ)))
print isidentity((ud1*(ux5+uy5)+ud2*(ux5^2+uy5^2))-((ux5+ux5^2)*(uy5+uy5^2))) or isidentity(uy1*uy1*uy2*uy3*ux1*ux1*ux2*ux3*((ud1*(ux5+uy5)+ud2*(ux5^2+uy5^2))-((ux5+ux5^2)*(uy5+uy5^2))))
print isidentity((ux5+uy5)-(uw5)) or isidentity(uy1*uy1*uy2*uy3*ux1*ux1*ux2*ux3*((ux5+uy5)-(uw5)))
print isidentity((ud1*(ux5+uy5)+ud2*(ux5^2+uy5^2))-((ux5+ux5^2)*(uy5+uy5^2))) or isidentity(uy1*uy1*uy2*uy3*ux1*ux1*ux2*ux3*((ud1*(ux5+uy5)+ud2*(ux5^2+uy5^2))-((ux5+ux5^2)*(uy5+uy5^2))))
print isidentity((ux5+uy5)-(uw5)) or isidentity(uy1*uy1*uy2*uy3*ux1*ux1*ux2*ux3*((ux5+uy5)-(uw5)))
Best operation counts
Smallest multiplication counts assuming I=10M, S=0M, *param=0M, add=0M, *const=0M:
12M for addition: 12M. 12M. 12M+6S.
10M for addition with Z2=1: 10M.
8M for addition with Z1=1 and Z2=1: 8M.
9M for readdition: 9M+3S after 12M+6S.
9M for readdition with Z2=1: 9M+3S after 12M+6S.
7M for readdition with Z1=1 and Z2=1: 7M after 8M.
6M for doubling: 6M+3S.
11M for tripling: 11M+4S.
12M for scaling: 1I+2M.
Smallest multiplication counts assuming I=10M, S=0.2M, *param=0M, add=0M, *const=0M:
12M for addition: 12M. 12M.
10M for addition with Z2=1: 10M.
8M for addition with Z1=1 and Z2=1: 8M.
9.6M for readdition: 9M+3S after 12M+6S.
9.6M for readdition with Z2=1: 9M+3S after 12M+6S.
7M for readdition with Z1=1 and Z2=1: 7M after 8M.
6.6M for doubling: 6M+3S.
11.8M for tripling: 11M+4S.
12M for scaling: 1I+2M.