# order of hyperelliptic curve divisor

I create a hyperelliptic curve, over finite field

zz = random_prime(2^81-1,False,2^80);
Q = GF(zz); x = Q['x'].gen();
f = x^5+ 2*x^2 +x + 3;
C = HyperellipticCurve(f, 0)


Then, Jacobian of Hyperelliptic Curve

J = C.jacobian()(Q)


then found two points and get there divisor and substract

P1 = (514014285438369163567791 : 461217828857546813804480 : 1)

P2 = (514014285438369163567791 : 461217828857546813804480 : 1)

D1 = J(P1);
D2 = J(P2);
D = D1 - D2;


but when calculating the order of D (error)

D.order()


otImplementedError
Traceback (most recent call last) <ipython-input-69-4132ea6bd39c> in <module>() ----> 1 D.order()

/home/sage/sage-8.0/src/sage/structure/element.pyx in sage.structure.element.AdditiveGroupElement.order (/home/sage/sage/src/build/cythonized/sage/structure/element.c:16098)() 2276 Return additive order of element 2277 """ -> 2278 return self.additive_order() 2279 2280 def __invert__(self):

/home/sage/sage-8.0/src/sage/structure/element.pyx in sage.structure.element.ModuleElement.additive_order (/home/sage/sage/src/build/cythonized/sage/structure/element.c:15332)() 2196 Return the additive order of self. 2197 """ -> 2198 raise NotImplementedError 2199 2200

###### #

NotImplementedError:

How to calculate it's order(I need the order to use it as mod in further calculation)

edit retag close merge delete

Sort by » oldest newest most voted

The order method is reminiscent by inheritance. (One should provide proper methods with "magic names", that are performing the task in the more specialized class. It is not the case in this case. This would be the simple answer to the failure of the order method. I still try to do something to find the order in a similar situation. I am trying to report as many details as possible, the situation should be improved in sage. Personally, i could not find the code line that hurts, and how to correct it.. A specialist should maybe look inside.)

In order to get a working order method, one has to implement it. For the general case, i could not find such a method. So the following solution is analyzing the special case, genus two, for the given situation.

The two points coincide. So getting the one random prime is a factorization, not an Euclidean algorithm. Let us get that prime:

S.<X> = ZZ[]
fX = X^5 + 2*X^2 + X + 3

x1, y1 = 514014285438369163567791, 461217828857546813804480
factor( y1^2 - fX(x1) )


This gives:

-1 * 17 * 241 * 636899873 * 1803619842798980267451757 * 7624191819494036880024145270844205070309439622966322479507656334034820178860673071


so the zz random prime is identified:

sage: 2^80 < 1803619842798980267451757
True
sage: 2^81 > 1803619842798980267451757
True


The other primes are not in the same range.

So we have the following concrete situation:

p = 1803619842798980267451757
F = GF(p)
R.<x> = F[]
f = x^5 + 2*x^2 + x + 3
C = HyperellipticCurve( f )
J = Jacobian( C )


Here, i would like to apply the formula (from the Frobenius action)

$$|J(\mathbb F_p)| = \frac 12\Big(\ |C(\mathbb F_{p^2})|+|C(\mathbb F_p)|^2\ \Big)-p \ ,$$

which relates the cardinalities of the corresponding sets of rational points on the hyperelliptic curve $C$, and on its Jacobian $J$.

In this particular case, the method

sage: C.count_points_hypellfrob( 2 )
---------------------------------------------------------------------------
NTLError                                  Traceback (most recent call last)


gave an NTLError, so we have a second problem in this case, possibly related to the big number $p$ (in my notation). Tracing back the error, C.frobenius_matrix_hypellfrob(N=2) is the (next) failing point.

Since i cannot solve both problems, here is only the solution for getting the right order for a "decent prime".

sage: p = (2^20).next_prime(); p
1048583


Then the same code works better:

p = 1048583
F = GF(p)
R.<x> = F[]
f = x^5 + 2*x^2 + x + 3
C = HyperellipticCurve( f )
J = Jacobian( C )
jac = J.point_set()


we get then:

sage: C.count_points(2)
[1049470, 1099525969626]


so the order of the rational points on the Jacobian is:

c1, c2 = C.count_points(2)
N = (c2+c1^2)/2 - p
N = ZZ(N)


This gives explicitly:

sage: N
1100455576680
sage: N.factor()
2^3 * 3 * 5 * 47 * 9769 * 19973


Let us now consider two points $P,Q$ on the curve, associate to them $[P]+ [Q]-2[O]$ on the jacobian, and associate multiples of this element.

CP = C.lift_x( -2017 )
CQ = C.lift_x( -2019 )

JP = J( CP )
JQ = J( CQ )
JR = JP + JQ

print "Order of the jacobian (GF(p)-rational points) is N = %s" % N
print "P is the point %s" % JP
print "Q is the point %s" % JQ
print "R = P+Q is the point %s" % JR

print "N*R = %s" % (N*JR)


We have the information:

Order of the jacobian (GF(p)-rational points) is N = 1100455576680
P is the point (x + 2017, y + 946267)
Q is the point (x + 2019, y + 773474)
R = P+Q is the point (x^2 + 4036*x + 926574, y + 610688*x + 618938)
N*R = (1)


Then:

for q in N.prime_divisors():
d = ZZ(N/q)
print "(%s) * R = %s" % (factor(d), d*JR)


This gives:

(2^2 * 3 * 5 * 47 * 9769 * 19973) * R = (1)
(2^3 * 5 * 47 * 9769 * 19973) * R = (1)
(2^3 * 3 * 47 * 9769 * 19973) * R = (x^2 + 93039*x + 768877, y + 177270*x + 668138)
(2^3 * 3 * 5 * 9769 * 19973) * R = (x^2 + 957487*x + 861022, y + 228398*x + 775371)
(2^3 * 3 * 5 * 47 * 19973) * R = (x^2 + 733076*x + 250096, y + 470322*x + 429613)
(2^3 * 3 * 5 * 47 * 9769) * R = (x^2 + 51468*x + 478817, y + 338851*x + 630462)


After some further pointed trials, we get the order, e.g. by interactively asking for the following

sage:     ZZ(N/6)*JR
(1)
sage:     ZZ(N/12)*JR
(1)
sage:     ZZ(N/24)*JR
(x + 297685, y)

more