Ask Your Question
1

order of hyperelliptic curve divisor

asked 2017-12-14 12:04:48 +0200

sherifasagewad gravatar image

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 flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2017-12-18 11:58:34 +0200

dan_fulea gravatar image

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)
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2017-12-14 12:04:48 +0200

Seen: 858 times

Last updated: Dec 18 '17