Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

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)