I've implemented Hessian Curve with Python
def checkPoint(P,p,c,d):
#X^3 + Y^3 + cZ^3 = dXYZ over GF(p)
if ( P[0]**3 + P[1]**3 + c * P[2]**3) % p == ( d * P[0] * P[1] * P[2] ) % p :
return True
return False
def bits(n):
while n:
yield n & 1
n >>= 1
def point_add( P, Q , p) :
if P is None or Q is None: # check for the zero point
return P or Q
#12M + 3add, consistent with the "12 multiplications" stated in 1986 Chudnovsky/Chudnovsky:
X3 = Q[0] * Q[2] * P[1]**2 - P[0] * P[2] * Q[1]**2
Y3 = Q[1] * Q[2] * P[0]**2 - P[1] * P[2] * Q[0]**2
Z3 = Q[0] * Q[1] * P[2]**2 - P[0] * P[1] * Q[2]**2
return ( X3 % p, Y3 % p, Z3 % p)
def point_double(P, p, c): #6M + 3S + 3add, consistent with the "9 multiplications" stated in 1986 Chudnovsky/Chudnovsky:
if P is None:
return None
X3 = P[1] * ( P[2]**3 - P[0]**3 )
Y3 = P[0] * ( P[1]**3 - P[2]**3 )
Z3 = P[2] * ( P[0]**3 - P[1]**3 )
return ( X3 % p, Y3 % p, Z3 % p)
def doubleAndAdd( G, k , p ,c):
addend = G
result = None
for b in bits(k) :
if b:
result = point_add(result, addend, p)
addend = point_double(addend, p, c)
return result
def findOrder(P, POI, p,c):
for i in range(2,1104601): # 1104601 upper range on the number of points
res = doubleAndAdd(P,i,p,c)
if res == POI:
print( "[",i,"]", P, "= ", res )
p = 1051
c = 1
d = 6
G = (4,2,6) #base point
Pinfinity = (1,1050,0) #(1,-1,0) inverse of O itself, inverse of (U,V,W) is (V,U,W)
print ( "d^3 == 27c? False expected : ", (d**3) % p == (27 *c) % p)
print("is point on the curve?", checkPoint(G,p,c,d))
findOrder(G, Pinfinity, p,c)
When I run this code, the result is
[ 77400 ] (4, 2, 6) = (1, 1050, 0)
[ 103500 ] (4, 2, 6) = (1, 1050, 0)
[ 153540 ] (4, 2, 6) = (1, 1050, 0)
[ 164340 ] (4, 2, 6) = (1, 1050, 0)
[ 169290 ] (4, 2, 6) = (1, 1050, 0)
[ 233640 ] (4, 2, 6) = (1, 1050, 0)
Normaly, if a point P has an order k then [k]P=O where O is the point at the infinity. And if you continue adding P to itself, one will get [2k]P=O, more generally it is [ x mod k]P
So if 77400 is order of P then [154800]P=0 but it is not
note : c=1 has no effect. It only contributes to point_double when c>1
I've figured out the problem, and the real solution is not easy. The order of the point (4,2,6) is 77400.
The problem relies on the implementation of the doubleAndAdd algorithm. Consider the starting point with G. The variables addend and result during the start and during the second visit for the point G are not the same since the addend was updated.
def doubleAndAdd( G, k , p ,c):
addend = G
result = None
for b in bits(k) :
if b:
result = point_add(result, addend, p)
addend = point_double(addend, p, c)
return result
Instead, I've updated the findOrder
def findOrder(P, POI, p,c):
#for i in range(2,1104601): # 1104601 upper range on the number of points
for i in range(1104601):
Gprime = doubleAndAdd(G,i,p,c)
if Gprime == POI:
print(i, " ", Gprime)
return i
So, it returns in the first hit of the Point at the Infinity as the order of the point.
The real solution requires the order of the base point beforehand, or better find the order of the curve since the order of any element dives the order of the curve by Lagrange Theorem. Once it is found, we can use the formula [ x mod k]P in the doubleAndAdd.
Note: there are existing Schoof's Algorithm in Python to count the number of points, however, one needs to change the Projective coordinates the Affine coordinates. Marc JoyeJean and Jacques Quisquater provided the formulas in