ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 18 Dec 2017 04:58:34 -0600order of hyperelliptic curve divisorhttp://ask.sagemath.org/question/40153/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)
Thu, 14 Dec 2017 05:04:48 -0600http://ask.sagemath.org/question/40153/order-of-hyperelliptic-curve-divisor/Answer by dan_fulea for <p>I create a hyperelliptic curve, over finite field</p>
<pre><code>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)
</code></pre>
<p>Then, Jacobian of Hyperelliptic Curve</p>
<pre><code>J = C.jacobian()(Q)
</code></pre>
<p>then found two points and get there divisor and substract</p>
<p>P1 = (514014285438369163567791 : 461217828857546813804480 : 1)</p>
<p>P2 = (514014285438369163567791 : 461217828857546813804480 : 1)</p>
<pre><code>D1 = J(P1);
D2 = J(P2);
D = D1 - D2;
</code></pre>
<p>but when calculating the order of D (error)</p>
<pre><code>D.order()
</code></pre>
<blockquote>
<p>otImplementedError <br>
Traceback (most recent call last)
<ipython-input-69-4132ea6bd39c> in
<module>()
----> 1 D.order()</p>
<p>/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):</p>
<p>/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</p>
<h6>#</h6>
<p>NotImplementedError:</p>
</blockquote>
<p>How to calculate it's order(I need the order to use it as mod in further calculation)</p>
http://ask.sagemath.org/question/40153/order-of-hyperelliptic-curve-divisor/?answer=40208#post-id-40208The `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)
Mon, 18 Dec 2017 04:58:34 -0600http://ask.sagemath.org/question/40153/order-of-hyperelliptic-curve-divisor/?answer=40208#post-id-40208