Hyperelliptic curves over a finite field¶
EXAMPLES:
sage: K.<a> = GF(9, 'a')
sage: x = polygen(K)
sage: C = HyperellipticCurve(x^7 - x^5 - 2, x^2 + a)
sage: C._points_fast_sqrt()
[(0 : 1 : 0), (a + 1 : a : 1), (a + 1 : a + 1 : 1), (2 : a + 1 : 1),
(2*a : 2*a + 2 : 1), (2*a : 2*a : 1), (1 : a + 1 : 1)]
>>> from sage.all import *
>>> K = GF(Integer(9), 'a', names=('a',)); (a,) = K._first_ngens(1)
>>> x = polygen(K)
>>> C = HyperellipticCurve(x**Integer(7) - x**Integer(5) - Integer(2), x**Integer(2) + a)
>>> C._points_fast_sqrt()
[(0 : 1 : 0), (a + 1 : a : 1), (a + 1 : a + 1 : 1), (2 : a + 1 : 1),
(2*a : 2*a + 2 : 1), (2*a : 2*a : 1), (1 : a + 1 : 1)]
K.<a> = GF(9, 'a') x = polygen(K) C = HyperellipticCurve(x^7 - x^5 - 2, x^2 + a) C._points_fast_sqrt()
AUTHORS:
David Kohel (2006)
Robert Bradshaw (2007)
Alyson Deines, Marina Gresham, Gagan Sekhon, (2010)
Daniel Krenn (2011)
Jean-Pierre Flori, Jan Tuitman (2013)
Kiran Kedlaya (2016)
Dean Bisogno (2017): Fixed Hasse-Witt computation
- class sage.schemes.hyperelliptic_curves.hyperelliptic_finite_field.HyperellipticCurve_finite_field(PP, f, h=None, names=None, genus=None)[source]¶
Bases:
HyperellipticCurve_generic,ProjectivePlaneCurve_finite_field- Cartier_matrix()[source]¶
INPUT:
self– Hyperelliptic Curve of the form \(y^2 = f(x)\) over a finite field, \(\GF{q}\)
OUTPUT:
The matrix \(M = (c_{pi-j})\), where \(c_i\) are the coefficients of \(f(x)^{(p-1)/2} = \sum c_i x^i\).
REFERENCES:
Yui. On the Jacobian varieties of hyperelliptic curves over fields of characteristic \(p > 2\).
EXAMPLES:
sage: K.<x> = GF(9,'x')[] sage: C = HyperellipticCurve(x^7 - 1, 0) sage: C.Cartier_matrix() [0 0 2] [0 0 0] [0 1 0] sage: K.<x> = GF(49, 'x')[] sage: C = HyperellipticCurve(x^5 + 1, 0) sage: C.Cartier_matrix() [0 3] [0 0] sage: P.<x> = GF(9, 'a')[] sage: E = HyperellipticCurve(x^29 + 1, 0) sage: E.Cartier_matrix() [0 0 1 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [1 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 1 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 1 0]
>>> from sage.all import * >>> K = GF(Integer(9),'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(7) - Integer(1), Integer(0)) >>> C.Cartier_matrix() [0 0 2] [0 0 0] [0 1 0] >>> K = GF(Integer(49), 'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(5) + Integer(1), Integer(0)) >>> C.Cartier_matrix() [0 3] [0 0] >>> P = GF(Integer(9), 'a')['x']; (x,) = P._first_ngens(1) >>> E = HyperellipticCurve(x**Integer(29) + Integer(1), Integer(0)) >>> E.Cartier_matrix() [0 0 1 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 1 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 1 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [1 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 1 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 1 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 1 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 1 0]
K.<x> = GF(9,'x')[] C = HyperellipticCurve(x^7 - 1, 0) C.Cartier_matrix() K.<x> = GF(49, 'x')[] C = HyperellipticCurve(x^5 + 1, 0) C.Cartier_matrix() P.<x> = GF(9, 'a')[] E = HyperellipticCurve(x^29 + 1, 0) E.Cartier_matrix()
- Hasse_Witt()[source]¶
INPUT:
self– Hyperelliptic Curve of the form \(y^2 = f(x)\) over a finite field, \(\GF{q}\)
OUTPUT:
The matrix \(N = M M^p \dots M^{p^{g-1}}\) where \(M = c_{pi-j}\), and \(f(x)^{(p-1)/2} = \sum c_i x^i\).
Reference-N. Yui. On the Jacobian varieties of hyperelliptic curves over fields of characteristic \(p > 2\).
EXAMPLES:
sage: K.<x> = GF(9, 'x')[] sage: C = HyperellipticCurve(x^7 - 1, 0) sage: C.Hasse_Witt() [0 0 0] [0 0 0] [0 0 0] sage: K.<x> = GF(49, 'x')[] sage: C = HyperellipticCurve(x^5 + 1, 0) sage: C.Hasse_Witt() [0 0] [0 0] sage: P.<x> = GF(9, 'a')[] sage: E = HyperellipticCurve(x^29 + 1, 0) sage: E.Hasse_Witt() [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
>>> from sage.all import * >>> K = GF(Integer(9), 'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(7) - Integer(1), Integer(0)) >>> C.Hasse_Witt() [0 0 0] [0 0 0] [0 0 0] >>> K = GF(Integer(49), 'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(5) + Integer(1), Integer(0)) >>> C.Hasse_Witt() [0 0] [0 0] >>> P = GF(Integer(9), 'a')['x']; (x,) = P._first_ngens(1) >>> E = HyperellipticCurve(x**Integer(29) + Integer(1), Integer(0)) >>> E.Hasse_Witt() [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0]
K.<x> = GF(9, 'x')[] C = HyperellipticCurve(x^7 - 1, 0) C.Hasse_Witt() K.<x> = GF(49, 'x')[] C = HyperellipticCurve(x^5 + 1, 0) C.Hasse_Witt() P.<x> = GF(9, 'a')[] E = HyperellipticCurve(x^29 + 1, 0) E.Hasse_Witt()
- a_number()[source]¶
INPUT:
self– Hyperelliptic Curve of the form \(y^2 = f(x)\) over a finite field, \(\GF{q}\)
OUTPUT: a-number
EXAMPLES:
sage: K.<x> = GF(49, 'x')[] sage: C = HyperellipticCurve(x^5 + 1, 0) sage: C.a_number() 1 sage: K.<x> = GF(9, 'x')[] sage: C = HyperellipticCurve(x^7 - 1, 0) sage: C.a_number() 1 sage: P.<x> = GF(9, 'a')[] sage: E = HyperellipticCurve(x^29 + 1, 0) sage: E.a_number() 5
>>> from sage.all import * >>> K = GF(Integer(49), 'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(5) + Integer(1), Integer(0)) >>> C.a_number() 1 >>> K = GF(Integer(9), 'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(7) - Integer(1), Integer(0)) >>> C.a_number() 1 >>> P = GF(Integer(9), 'a')['x']; (x,) = P._first_ngens(1) >>> E = HyperellipticCurve(x**Integer(29) + Integer(1), Integer(0)) >>> E.a_number() 5
K.<x> = GF(49, 'x')[] C = HyperellipticCurve(x^5 + 1, 0) C.a_number() K.<x> = GF(9, 'x')[] C = HyperellipticCurve(x^7 - 1, 0) C.a_number() P.<x> = GF(9, 'a')[] E = HyperellipticCurve(x^29 + 1, 0) E.a_number()
- cardinality(extension_degree=1)[source]¶
Count points on a single extension of the base field.
EXAMPLES:
sage: # needs sage.libs.ntl sage.libs.linbox sage: K = GF(101) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + 3*t^5 + 5) sage: H.cardinality() 106 sage: H.cardinality(15) 1160968955369992567076405831000 sage: H.cardinality(100) 270481382942152609326719471080753083367793838278100277689020104911710151430673927943945601434674459120495370826289654897190781715493352266982697064575800553229661690000887425442240414673923744999504000 sage: # needs sage.libs.ntl sage.libs.linbox sage: K = GF(37) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + 3*t^5 + 5) sage: H.cardinality() 40 sage: H.cardinality(2) 1408 sage: H.cardinality(3) 50116
>>> from sage.all import * >>> # needs sage.libs.ntl sage.libs.linbox >>> K = GF(Integer(101)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.cardinality() 106 >>> H.cardinality(Integer(15)) 1160968955369992567076405831000 >>> H.cardinality(Integer(100)) 270481382942152609326719471080753083367793838278100277689020104911710151430673927943945601434674459120495370826289654897190781715493352266982697064575800553229661690000887425442240414673923744999504000 >>> # needs sage.libs.ntl sage.libs.linbox >>> K = GF(Integer(37)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.cardinality() 40 >>> H.cardinality(Integer(2)) 1408 >>> H.cardinality(Integer(3)) 50116
# needs sage.libs.ntl sage.libs.linbox K = GF(101) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + 3*t^5 + 5) H.cardinality() H.cardinality(15) H.cardinality(100) # needs sage.libs.ntl sage.libs.linbox K = GF(37) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + 3*t^5 + 5) H.cardinality() H.cardinality(2) H.cardinality(3)
The following example shows that upstream Issue #20391 has been resolved:
sage: # needs sage.libs.ntl sage.libs.linbox sage: F = GF(23) sage: x = polygen(F) sage: C = HyperellipticCurve(x^8 + 1) sage: C.cardinality() 24
>>> from sage.all import * >>> # needs sage.libs.ntl sage.libs.linbox >>> F = GF(Integer(23)) >>> x = polygen(F) >>> C = HyperellipticCurve(x**Integer(8) + Integer(1)) >>> C.cardinality() 24
# needs sage.libs.ntl sage.libs.linbox F = GF(23) x = polygen(F) C = HyperellipticCurve(x^8 + 1) C.cardinality()
- cardinality_exhaustive(extension_degree=1, algorithm=None)[source]¶
Count points on a single extension of the base field by enumerating over x and solving the resulting quadratic equation for y.
EXAMPLES:
sage: K.<a> = GF(9, 'a') sage: x = polygen(K) sage: C = HyperellipticCurve(x^7 - 1, x^2 + a) sage: C.cardinality_exhaustive() 7 sage: K = GF(next_prime(1<<10)) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^7 + 3*t^5 + 5) sage: H.cardinality_exhaustive() 1025 sage: P.<x> = PolynomialRing(GF(9,'a')) sage: H = HyperellipticCurve(x^5+x^2+1) sage: H.count_points(5) [18, 78, 738, 6366, 60018] sage: F.<a> = GF(4); P.<x> = F[] sage: H = HyperellipticCurve(x^5+a*x^2+1, x+a+1) sage: H.count_points(6) [2, 24, 74, 256, 1082, 4272]
>>> from sage.all import * >>> K = GF(Integer(9), 'a', names=('a',)); (a,) = K._first_ngens(1) >>> x = polygen(K) >>> C = HyperellipticCurve(x**Integer(7) - Integer(1), x**Integer(2) + a) >>> C.cardinality_exhaustive() 7 >>> K = GF(next_prime(Integer(1)<<Integer(10))) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(7) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.cardinality_exhaustive() 1025 >>> P = PolynomialRing(GF(Integer(9),'a'), names=('x',)); (x,) = P._first_ngens(1) >>> H = HyperellipticCurve(x**Integer(5)+x**Integer(2)+Integer(1)) >>> H.count_points(Integer(5)) [18, 78, 738, 6366, 60018] >>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1); P = F['x']; (x,) = P._first_ngens(1) >>> H = HyperellipticCurve(x**Integer(5)+a*x**Integer(2)+Integer(1), x+a+Integer(1)) >>> H.count_points(Integer(6)) [2, 24, 74, 256, 1082, 4272]
K.<a> = GF(9, 'a') x = polygen(K) C = HyperellipticCurve(x^7 - 1, x^2 + a) C.cardinality_exhaustive() K = GF(next_prime(1<<10)) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^7 + 3*t^5 + 5) H.cardinality_exhaustive() P.<x> = PolynomialRing(GF(9,'a')) H = HyperellipticCurve(x^5+x^2+1) H.count_points(5) F.<a> = GF(4); P.<x> = F[] H = HyperellipticCurve(x^5+a*x^2+1, x+a+1) H.count_points(6)
- cardinality_hypellfrob(extension_degree=1, algorithm=None)[source]¶
Count points on a single extension of the base field using the
hypellfrobprogram.EXAMPLES:
sage: K = GF(next_prime(1<<10)) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^7 + 3*t^5 + 5) sage: H.cardinality_hypellfrob() # needs sage.libs.ntl sage.libs.linbox 1025 sage: K = GF(49999) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^7 + 3*t^5 + 5) sage: H.cardinality_hypellfrob() # needs sage.libs.ntl sage.libs.linbox 50162 sage: H.cardinality_hypellfrob(3) # needs sage.libs.ntl sage.libs.linbox 124992471088310
>>> from sage.all import * >>> K = GF(next_prime(Integer(1)<<Integer(10))) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(7) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.cardinality_hypellfrob() # needs sage.libs.ntl sage.libs.linbox 1025 >>> K = GF(Integer(49999)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(7) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.cardinality_hypellfrob() # needs sage.libs.ntl sage.libs.linbox 50162 >>> H.cardinality_hypellfrob(Integer(3)) # needs sage.libs.ntl sage.libs.linbox 124992471088310
K = GF(next_prime(1<<10)) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^7 + 3*t^5 + 5) H.cardinality_hypellfrob() # needs sage.libs.ntl sage.libs.linbox K = GF(49999) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^7 + 3*t^5 + 5) H.cardinality_hypellfrob() # needs sage.libs.ntl sage.libs.linbox H.cardinality_hypellfrob(3) # needs sage.libs.ntl sage.libs.linbox
- count_points(n=1)[source]¶
Count points over finite fields.
INPUT:
n– integer
OUTPUT:
An integer. The number of points over \(\GF{q}, \ldots, \GF{q^n}\) on a hyperelliptic curve over a finite field \(\GF{q}\).
Warning
This is currently using exhaustive search for hyperelliptic curves over non-prime fields, which can be awfully slow.
EXAMPLES:
sage: P.<x> = PolynomialRing(GF(3)) sage: C = HyperellipticCurve(x^3+x^2+1) sage: C.count_points(4) [6, 12, 18, 96] sage: C.base_extend(GF(9,'a')).count_points(2) [12, 96] sage: K = GF(2**31-1) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^5 + 3*t + 5) sage: H.count_points() # long time, 2.4 sec on a Corei7 # needs sage.libs.ntl sage.libs.linbox [2147464821] sage: H.count_points(n=2) # long time, 30s on a Corei7 # needs sage.libs.ntl sage.libs.linbox [2147464821, 4611686018988310237] sage: K = GF(2**7-1) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^13 + 3*t^5 + 5) sage: H.count_points(n=6) # needs sage.libs.ntl sage.libs.linbox [112, 16360, 2045356, 260199160, 33038302802, 4195868633548] sage: P.<x> = PolynomialRing(GF(3)) sage: H = HyperellipticCurve(x^3+x^2+1) sage: C1 = H.count_points(4); C1 # needs sage.libs.ntl sage.libs.linbox [6, 12, 18, 96] sage: C2 = sage.schemes.generic.scheme.Scheme.count_points(H,4); C2 # long time, 2s on a Corei7 [6, 12, 18, 96] sage: C1 == C2 # long time, because we need C2 to be defined True sage: P.<x> = PolynomialRing(GF(9,'a')) sage: H = HyperellipticCurve(x^5+x^2+1) sage: H.count_points(5) [18, 78, 738, 6366, 60018] sage: F.<a> = GF(4); P.<x> = F[] sage: H = HyperellipticCurve(x^5+a*x^2+1, x+a+1) sage: H.count_points(6) [2, 24, 74, 256, 1082, 4272]
>>> from sage.all import * >>> P = PolynomialRing(GF(Integer(3)), names=('x',)); (x,) = P._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(3)+x**Integer(2)+Integer(1)) >>> C.count_points(Integer(4)) [6, 12, 18, 96] >>> C.base_extend(GF(Integer(9),'a')).count_points(Integer(2)) [12, 96] >>> K = GF(Integer(2)**Integer(31)-Integer(1)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + Integer(3)*t + Integer(5)) >>> H.count_points() # long time, 2.4 sec on a Corei7 # needs sage.libs.ntl sage.libs.linbox [2147464821] >>> H.count_points(n=Integer(2)) # long time, 30s on a Corei7 # needs sage.libs.ntl sage.libs.linbox [2147464821, 4611686018988310237] >>> K = GF(Integer(2)**Integer(7)-Integer(1)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(13) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.count_points(n=Integer(6)) # needs sage.libs.ntl sage.libs.linbox [112, 16360, 2045356, 260199160, 33038302802, 4195868633548] >>> P = PolynomialRing(GF(Integer(3)), names=('x',)); (x,) = P._first_ngens(1) >>> H = HyperellipticCurve(x**Integer(3)+x**Integer(2)+Integer(1)) >>> C1 = H.count_points(Integer(4)); C1 # needs sage.libs.ntl sage.libs.linbox [6, 12, 18, 96] >>> C2 = sage.schemes.generic.scheme.Scheme.count_points(H,Integer(4)); C2 # long time, 2s on a Corei7 [6, 12, 18, 96] >>> C1 == C2 # long time, because we need C2 to be defined True >>> P = PolynomialRing(GF(Integer(9),'a'), names=('x',)); (x,) = P._first_ngens(1) >>> H = HyperellipticCurve(x**Integer(5)+x**Integer(2)+Integer(1)) >>> H.count_points(Integer(5)) [18, 78, 738, 6366, 60018] >>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1); P = F['x']; (x,) = P._first_ngens(1) >>> H = HyperellipticCurve(x**Integer(5)+a*x**Integer(2)+Integer(1), x+a+Integer(1)) >>> H.count_points(Integer(6)) [2, 24, 74, 256, 1082, 4272]
P.<x> = PolynomialRing(GF(3)) C = HyperellipticCurve(x^3+x^2+1) C.count_points(4) C.base_extend(GF(9,'a')).count_points(2) K = GF(2**31-1) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^5 + 3*t + 5) H.count_points() # long time, 2.4 sec on a Corei7 # needs sage.libs.ntl sage.libs.linbox H.count_points(n=2) # long time, 30s on a Corei7 # needs sage.libs.ntl sage.libs.linbox K = GF(2**7-1) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^13 + 3*t^5 + 5) H.count_points(n=6) # needs sage.libs.ntl sage.libs.linbox P.<x> = PolynomialRing(GF(3)) H = HyperellipticCurve(x^3+x^2+1) C1 = H.count_points(4); C1 # needs sage.libs.ntl sage.libs.linbox C2 = sage.schemes.generic.scheme.Scheme.count_points(H,4); C2 # long time, 2s on a Corei7 C1 == C2 # long time, because we need C2 to be defined P.<x> = PolynomialRing(GF(9,'a')) H = HyperellipticCurve(x^5+x^2+1) H.count_points(5) F.<a> = GF(4); P.<x> = F[] H = HyperellipticCurve(x^5+a*x^2+1, x+a+1) H.count_points(6)
This example shows that upstream Issue #20391 is resolved:
sage: x = polygen(GF(4099)) sage: H = HyperellipticCurve(x^6 + x + 1) sage: H.count_points(1) # needs sage.libs.ntl sage.libs.linbox [4106]
>>> from sage.all import * >>> x = polygen(GF(Integer(4099))) >>> H = HyperellipticCurve(x**Integer(6) + x + Integer(1)) >>> H.count_points(Integer(1)) # needs sage.libs.ntl sage.libs.linbox [4106]
x = polygen(GF(4099)) H = HyperellipticCurve(x^6 + x + 1) H.count_points(1) # needs sage.libs.ntl sage.libs.linbox
- count_points_exhaustive(n=1, naive=False)[source]¶
Count the number of points on the curve over the first \(n\) extensions of the base field by exhaustive search if \(n\) if smaller than \(g\), the genus of the curve, and by computing the frobenius polynomial after performing exhaustive search on the first \(g\) extensions if \(n > g\) (unless
naive == True).EXAMPLES:
sage: K = GF(5) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + t^3 + 1) sage: H.count_points_exhaustive(n=5) [9, 27, 108, 675, 3069]
>>> from sage.all import * >>> K = GF(Integer(5)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + t**Integer(3) + Integer(1)) >>> H.count_points_exhaustive(n=Integer(5)) [9, 27, 108, 675, 3069]
K = GF(5) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + t^3 + 1) H.count_points_exhaustive(n=5)
When \(n > g\), the frobenius polynomial is computed from the numbers of points of the curve over the first \(g\) extension, so that computing the number of points on extensions of degree \(n > g\) is not much more expensive than for \(n == g\):
sage: H.count_points_exhaustive(n=15) [9, 27, 108, 675, 3069, 16302, 78633, 389475, 1954044, 9768627, 48814533, 244072650, 1220693769, 6103414827, 30517927308]
>>> from sage.all import * >>> H.count_points_exhaustive(n=Integer(15)) [9, 27, 108, 675, 3069, 16302, 78633, 389475, 1954044, 9768627, 48814533, 244072650, 1220693769, 6103414827, 30517927308]
H.count_points_exhaustive(n=15)
This behavior can be disabled by passing
naive=True:sage: H.count_points_exhaustive(n=6, naive=True) # long time, 7s on a Corei7 [9, 27, 108, 675, 3069, 16302]
>>> from sage.all import * >>> H.count_points_exhaustive(n=Integer(6), naive=True) # long time, 7s on a Corei7 [9, 27, 108, 675, 3069, 16302]
H.count_points_exhaustive(n=6, naive=True) # long time, 7s on a Corei7
- count_points_frobenius_polynomial(n=1, f=None)[source]¶
Count the number of points on the curve over the first \(n\) extensions of the base field by computing the frobenius polynomial.
EXAMPLES:
sage: K = GF(49999) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^19 + t + 1)
>>> from sage.all import * >>> K = GF(Integer(49999)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(19) + t + Integer(1))
K = GF(49999) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^19 + t + 1)
The following computation takes a long time as the complete characteristic polynomial of the frobenius is computed:
sage: H.count_points_frobenius_polynomial(3) # long time, 20s on a Corei7 (when computed before the following test of course) [49491, 2500024375, 124992509154249]
>>> from sage.all import * >>> H.count_points_frobenius_polynomial(Integer(3)) # long time, 20s on a Corei7 (when computed before the following test of course) [49491, 2500024375, 124992509154249]
H.count_points_frobenius_polynomial(3) # long time, 20s on a Corei7 (when computed before the following test of course)
As the polynomial is cached, further computations of number of points are really fast:
sage: H.count_points_frobenius_polynomial(19) # long time, because of the previous test [49491, 2500024375, 124992509154249, 6249500007135192947, 312468751250758776051811, 15623125093747382662737313867, 781140631562281338861289572576257, 39056250437482500417107992413002794587, 1952773465623687539373429411200893147181079, 97636720507718753281169963459063147221761552935, 4881738388665429945305281187129778704058864736771824, 244082037694882831835318764490138139735446240036293092851, 12203857802706446708934102903106811520015567632046432103159713, 610180686277519628999996211052002771035439565767719719151141201339, 30508424133189703930370810556389262704405225546438978173388673620145499, 1525390698235352006814610157008906752699329454643826047826098161898351623931, 76268009521069364988723693240288328729528917832735078791261015331201838856825193, 3813324208043947180071195938321176148147244128062172555558715783649006587868272993991, 190662397077989315056379725720120486231213267083935859751911720230901597698389839098903847]
>>> from sage.all import * >>> H.count_points_frobenius_polynomial(Integer(19)) # long time, because of the previous test [49491, 2500024375, 124992509154249, 6249500007135192947, 312468751250758776051811, 15623125093747382662737313867, 781140631562281338861289572576257, 39056250437482500417107992413002794587, 1952773465623687539373429411200893147181079, 97636720507718753281169963459063147221761552935, 4881738388665429945305281187129778704058864736771824, 244082037694882831835318764490138139735446240036293092851, 12203857802706446708934102903106811520015567632046432103159713, 610180686277519628999996211052002771035439565767719719151141201339, 30508424133189703930370810556389262704405225546438978173388673620145499, 1525390698235352006814610157008906752699329454643826047826098161898351623931, 76268009521069364988723693240288328729528917832735078791261015331201838856825193, 3813324208043947180071195938321176148147244128062172555558715783649006587868272993991, 190662397077989315056379725720120486231213267083935859751911720230901597698389839098903847]
H.count_points_frobenius_polynomial(19) # long time, because of the previous test
- count_points_hypellfrob(n=1, N=None, algorithm=None)[source]¶
Count the number of points on the curve over the first \(n\) extensions of the base field using the
hypellfrobprogram.This only supports prime fields of large enough characteristic.
EXAMPLES:
sage: # needs sage.libs.ntl sage.libs.linbox sage: K = GF(49999) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^21 + 3*t^5 + 5) sage: H.count_points_hypellfrob() [49804] sage: H.count_points_hypellfrob(2) [49804, 2499799038] sage: # needs sage.libs.ntl sage.libs.linbox sage: K = GF(2**7-1) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^11 + 3*t^5 + 5) sage: H.count_points_hypellfrob() [127] sage: H.count_points_hypellfrob(n=5) [127, 16335, 2045701, 260134299, 33038098487] sage: # needs sage.libs.ntl sage.libs.linbox sage: K = GF(2**7-1) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^13 + 3*t^5 + 5) sage: H.count_points(n=6) [112, 16360, 2045356, 260199160, 33038302802, 4195868633548]
>>> from sage.all import * >>> # needs sage.libs.ntl sage.libs.linbox >>> K = GF(Integer(49999)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(21) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.count_points_hypellfrob() [49804] >>> H.count_points_hypellfrob(Integer(2)) [49804, 2499799038] >>> # needs sage.libs.ntl sage.libs.linbox >>> K = GF(Integer(2)**Integer(7)-Integer(1)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(11) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.count_points_hypellfrob() [127] >>> H.count_points_hypellfrob(n=Integer(5)) [127, 16335, 2045701, 260134299, 33038098487] >>> # needs sage.libs.ntl sage.libs.linbox >>> K = GF(Integer(2)**Integer(7)-Integer(1)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(13) + Integer(3)*t**Integer(5) + Integer(5)) >>> H.count_points(n=Integer(6)) [112, 16360, 2045356, 260199160, 33038302802, 4195868633548]
# needs sage.libs.ntl sage.libs.linbox K = GF(49999) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^21 + 3*t^5 + 5) H.count_points_hypellfrob() H.count_points_hypellfrob(2) # needs sage.libs.ntl sage.libs.linbox K = GF(2**7-1) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^11 + 3*t^5 + 5) H.count_points_hypellfrob() H.count_points_hypellfrob(n=5) # needs sage.libs.ntl sage.libs.linbox K = GF(2**7-1) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^13 + 3*t^5 + 5) H.count_points(n=6)
The base field should be prime:
sage: K.<z> = GF(19**10) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + (z+1)*t^5 + 1) sage: H.count_points_hypellfrob() Traceback (most recent call last): ... ValueError: hypellfrob does not support non-prime fields
>>> from sage.all import * >>> K = GF(Integer(19)**Integer(10), names=('z',)); (z,) = K._first_ngens(1) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + (z+Integer(1))*t**Integer(5) + Integer(1)) >>> H.count_points_hypellfrob() Traceback (most recent call last): ... ValueError: hypellfrob does not support non-prime fields
K.<z> = GF(19**10) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + (z+1)*t^5 + 1) H.count_points_hypellfrob()
and the characteristic should be large enough:
sage: K = GF(7) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + t^3 + 1) sage: H.count_points_hypellfrob() Traceback (most recent call last): ... ValueError: p=7 should be greater than (2*g+1)(2*N-1)=27
>>> from sage.all import * >>> K = GF(Integer(7)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + t**Integer(3) + Integer(1)) >>> H.count_points_hypellfrob() Traceback (most recent call last): ... ValueError: p=7 should be greater than (2*g+1)(2*N-1)=27
K = GF(7) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + t^3 + 1) H.count_points_hypellfrob()
- count_points_matrix_traces(n=1, M=None, N=None)[source]¶
Count the number of points on the curve over the first \(n\) extensions of the base field by computing traces of powers of the frobenius matrix. This requires less \(p\)-adic precision than computing the charpoly of the matrix when \(n < g\) where \(g\) is the genus of the curve.
EXAMPLES:
sage: K = GF(49999) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^19 + t + 1) sage: H.count_points_matrix_traces(3) # needs sage.libs.ntl sage.libs.linbox [49491, 2500024375, 124992509154249]
>>> from sage.all import * >>> K = GF(Integer(49999)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(19) + t + Integer(1)) >>> H.count_points_matrix_traces(Integer(3)) # needs sage.libs.ntl sage.libs.linbox [49491, 2500024375, 124992509154249]
K = GF(49999) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^19 + t + 1) H.count_points_matrix_traces(3) # needs sage.libs.ntl sage.libs.linbox
- frobenius_matrix(N=None, algorithm='hypellfrob')[source]¶
Compute \(p\)-adic frobenius matrix to precision \(p^N\). If \(N\) not supplied, a default value is selected, which is the minimum needed to recover the charpoly unambiguously.
Note
Currently only implemented using
hypellfrob, which means it only works over the prime field \(GF(p)\), and requires \(p > (2g+1)(2N-1)\).EXAMPLES:
sage: R.<t> = PolynomialRing(GF(37)) sage: H = HyperellipticCurve(t^5 + t + 2) sage: H.frobenius_matrix() # needs sage.libs.ntl sage.libs.linbox [1258 + O(37^2) 925 + O(37^2) 132 + O(37^2) 587 + O(37^2)] [1147 + O(37^2) 814 + O(37^2) 241 + O(37^2) 1011 + O(37^2)] [1258 + O(37^2) 1184 + O(37^2) 1105 + O(37^2) 482 + O(37^2)] [1073 + O(37^2) 999 + O(37^2) 772 + O(37^2) 929 + O(37^2)]
>>> from sage.all import * >>> R = PolynomialRing(GF(Integer(37)), names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + t + Integer(2)) >>> H.frobenius_matrix() # needs sage.libs.ntl sage.libs.linbox [1258 + O(37^2) 925 + O(37^2) 132 + O(37^2) 587 + O(37^2)] [1147 + O(37^2) 814 + O(37^2) 241 + O(37^2) 1011 + O(37^2)] [1258 + O(37^2) 1184 + O(37^2) 1105 + O(37^2) 482 + O(37^2)] [1073 + O(37^2) 999 + O(37^2) 772 + O(37^2) 929 + O(37^2)]
R.<t> = PolynomialRing(GF(37)) H = HyperellipticCurve(t^5 + t + 2) H.frobenius_matrix() # needs sage.libs.ntl sage.libs.linbox
The
hypellfrobprogram doesn’t support non-prime fields:sage: K.<z> = GF(37**3) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + z*t^3 + 1) sage: H.frobenius_matrix(algorithm='hypellfrob') Traceback (most recent call last): ... NotImplementedError: Computation of Frobenius matrix only implemented for hyperelliptic curves defined over prime fields.
>>> from sage.all import * >>> K = GF(Integer(37)**Integer(3), names=('z',)); (z,) = K._first_ngens(1) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + z*t**Integer(3) + Integer(1)) >>> H.frobenius_matrix(algorithm='hypellfrob') Traceback (most recent call last): ... NotImplementedError: Computation of Frobenius matrix only implemented for hyperelliptic curves defined over prime fields.
K.<z> = GF(37**3) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + z*t^3 + 1) H.frobenius_matrix(algorithm='hypellfrob')
nor too small characteristic:
sage: K = GF(7) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + t^3 + 1) sage: H.frobenius_matrix(algorithm='hypellfrob') # needs sage.libs.ntl sage.libs.linbox Traceback (most recent call last): ... ValueError: In the current implementation, p must be greater than (2g+1)(2N-1) = 81
>>> from sage.all import * >>> K = GF(Integer(7)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + t**Integer(3) + Integer(1)) >>> H.frobenius_matrix(algorithm='hypellfrob') # needs sage.libs.ntl sage.libs.linbox Traceback (most recent call last): ... ValueError: In the current implementation, p must be greater than (2g+1)(2N-1) = 81
K = GF(7) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + t^3 + 1) H.frobenius_matrix(algorithm='hypellfrob') # needs sage.libs.ntl sage.libs.linbox
- frobenius_matrix_hypellfrob(N=None)[source]¶
Compute \(p\)-adic frobenius matrix to precision \(p^N\). If \(N\) not supplied, a default value is selected, which is the minimum needed to recover the charpoly unambiguously.
Note
Implemented using
hypellfrob, which means it only works over the prime field \(GF(p)\), and requires \(p > (2g+1)(2N-1)\).EXAMPLES:
sage: R.<t> = PolynomialRing(GF(37)) sage: H = HyperellipticCurve(t^5 + t + 2) sage: H.frobenius_matrix_hypellfrob() # needs sage.libs.ntl sage.libs.linbox [1258 + O(37^2) 925 + O(37^2) 132 + O(37^2) 587 + O(37^2)] [1147 + O(37^2) 814 + O(37^2) 241 + O(37^2) 1011 + O(37^2)] [1258 + O(37^2) 1184 + O(37^2) 1105 + O(37^2) 482 + O(37^2)] [1073 + O(37^2) 999 + O(37^2) 772 + O(37^2) 929 + O(37^2)]
>>> from sage.all import * >>> R = PolynomialRing(GF(Integer(37)), names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + t + Integer(2)) >>> H.frobenius_matrix_hypellfrob() # needs sage.libs.ntl sage.libs.linbox [1258 + O(37^2) 925 + O(37^2) 132 + O(37^2) 587 + O(37^2)] [1147 + O(37^2) 814 + O(37^2) 241 + O(37^2) 1011 + O(37^2)] [1258 + O(37^2) 1184 + O(37^2) 1105 + O(37^2) 482 + O(37^2)] [1073 + O(37^2) 999 + O(37^2) 772 + O(37^2) 929 + O(37^2)]
R.<t> = PolynomialRing(GF(37)) H = HyperellipticCurve(t^5 + t + 2) H.frobenius_matrix_hypellfrob() # needs sage.libs.ntl sage.libs.linbox
The
hypellfrobprogram doesn’t support non-prime fields:sage: K.<z> = GF(37**3) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + z*t^3 + 1) sage: H.frobenius_matrix_hypellfrob() Traceback (most recent call last): ... NotImplementedError: Computation of Frobenius matrix only implemented for hyperelliptic curves defined over prime fields.
>>> from sage.all import * >>> K = GF(Integer(37)**Integer(3), names=('z',)); (z,) = K._first_ngens(1) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + z*t**Integer(3) + Integer(1)) >>> H.frobenius_matrix_hypellfrob() Traceback (most recent call last): ... NotImplementedError: Computation of Frobenius matrix only implemented for hyperelliptic curves defined over prime fields.
K.<z> = GF(37**3) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + z*t^3 + 1) H.frobenius_matrix_hypellfrob()
nor too small characteristic:
sage: K = GF(7) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^9 + t^3 + 1) sage: H.frobenius_matrix_hypellfrob() # needs sage.libs.ntl sage.libs.linbox Traceback (most recent call last): ... ValueError: In the current implementation, p must be greater than (2g+1)(2N-1) = 81
>>> from sage.all import * >>> K = GF(Integer(7)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + t**Integer(3) + Integer(1)) >>> H.frobenius_matrix_hypellfrob() # needs sage.libs.ntl sage.libs.linbox Traceback (most recent call last): ... ValueError: In the current implementation, p must be greater than (2g+1)(2N-1) = 81
K = GF(7) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^9 + t^3 + 1) H.frobenius_matrix_hypellfrob() # needs sage.libs.ntl sage.libs.linbox
- frobenius_polynomial(algorithm=None, **kwargs)[source]¶
Compute the charpoly of frobenius, as an element of \(\ZZ[x]\).
INPUT:
algorithm– the algorithm to use, one ofNone(default) – automatically select an algorithm.'pari'– use the PARI functionhyperellcharpoly.'cardinalities'– compute the number of points on the curve over \(g\) extensions of the base field where \(g\) is the genus of the curve.Warning
This is highly inefficient when the base field or the genus of the curve are large.
'matrix'– compute the charpoly of the frobenius matrix.This is currently only supported when the base field is prime and large enough using the
hypellfroblibrary.
**kwargs– additional keyword arguments passed to the internal method. Undocumented feature, may be removed in the future.
EXAMPLES:
sage: R.<t> = PolynomialRing(GF(37)) sage: H = HyperellipticCurve(t^5 + t + 2) sage: H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox x^4 + x^3 - 52*x^2 + 37*x + 1369
>>> from sage.all import * >>> R = PolynomialRing(GF(Integer(37)), names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + t + Integer(2)) >>> H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox x^4 + x^3 - 52*x^2 + 37*x + 1369
R.<t> = PolynomialRing(GF(37)) H = HyperellipticCurve(t^5 + t + 2) H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox
A quadratic twist:
sage: H = HyperellipticCurve(2*t^5 + 2*t + 4) sage: H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox x^4 - x^3 - 52*x^2 - 37*x + 1369
>>> from sage.all import * >>> H = HyperellipticCurve(Integer(2)*t**Integer(5) + Integer(2)*t + Integer(4)) >>> H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox x^4 - x^3 - 52*x^2 - 37*x + 1369
H = HyperellipticCurve(2*t^5 + 2*t + 4) H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox
Slightly larger example:
sage: K = GF(2003) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^7 + 487*t^5 + 9*t + 1) sage: H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox x^6 - 14*x^5 + 1512*x^4 - 66290*x^3 + 3028536*x^2 - 56168126*x + 8036054027
>>> from sage.all import * >>> K = GF(Integer(2003)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(7) + Integer(487)*t**Integer(5) + Integer(9)*t + Integer(1)) >>> H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox x^6 - 14*x^5 + 1512*x^4 - 66290*x^3 + 3028536*x^2 - 56168126*x + 8036054027
K = GF(2003) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^7 + 487*t^5 + 9*t + 1) H.frobenius_polynomial() # needs sage.libs.ntl sage.libs.linbox
Curves defined over a non-prime field of odd characteristic, or an odd prime field which is too small compared to the genus, are supported via PARI:
sage: K.<z> = GF(23**3) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^3 + z*t + 4) sage: H.frobenius_polynomial() x^2 - 15*x + 12167 sage: K.<z> = GF(3**3) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^5 + z*t + z**3) sage: H.frobenius_polynomial() x^4 - 3*x^3 + 10*x^2 - 81*x + 729
>>> from sage.all import * >>> K = GF(Integer(23)**Integer(3), names=('z',)); (z,) = K._first_ngens(1) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(3) + z*t + Integer(4)) >>> H.frobenius_polynomial() x^2 - 15*x + 12167 >>> K = GF(Integer(3)**Integer(3), names=('z',)); (z,) = K._first_ngens(1) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + z*t + z**Integer(3)) >>> H.frobenius_polynomial() x^4 - 3*x^3 + 10*x^2 - 81*x + 729
K.<z> = GF(23**3) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^3 + z*t + 4) H.frobenius_polynomial() K.<z> = GF(3**3) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^5 + z*t + z**3) H.frobenius_polynomial()
Over prime fields of odd characteristic, \(h\) may be nonzero:
sage: K = GF(101) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^5 + 27*t + 3, t) sage: H.frobenius_polynomial() x^4 + 2*x^3 - 58*x^2 + 202*x + 10201
>>> from sage.all import * >>> K = GF(Integer(101)) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + Integer(27)*t + Integer(3), t) >>> H.frobenius_polynomial() x^4 + 2*x^3 - 58*x^2 + 202*x + 10201
K = GF(101) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^5 + 27*t + 3, t) H.frobenius_polynomial()
Over prime fields of odd characteristic, \(f\) may have even degree:
sage: H = HyperellipticCurve(t^6 + 27*t + 3) sage: H.frobenius_polynomial() x^4 + 25*x^3 + 322*x^2 + 2525*x + 10201
>>> from sage.all import * >>> H = HyperellipticCurve(t**Integer(6) + Integer(27)*t + Integer(3)) >>> H.frobenius_polynomial() x^4 + 25*x^3 + 322*x^2 + 2525*x + 10201
H = HyperellipticCurve(t^6 + 27*t + 3) H.frobenius_polynomial()
In even characteristic, the naive algorithm could cover all cases because we can easily check for squareness in quotient rings of polynomial rings over finite fields but these rings unfortunately do not support iteration:
sage: K.<z> = GF(2**5) sage: R.<t> = PolynomialRing(K) sage: H = HyperellipticCurve(t^5 + z*t + z**3, t) sage: H.frobenius_polynomial() x^4 - x^3 + 16*x^2 - 32*x + 1024
>>> from sage.all import * >>> K = GF(Integer(2)**Integer(5), names=('z',)); (z,) = K._first_ngens(1) >>> R = PolynomialRing(K, names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + z*t + z**Integer(3), t) >>> H.frobenius_polynomial() x^4 - x^3 + 16*x^2 - 32*x + 1024
K.<z> = GF(2**5) R.<t> = PolynomialRing(K) H = HyperellipticCurve(t^5 + z*t + z**3, t) H.frobenius_polynomial()
- frobenius_polynomial_cardinalities(*args, **kwds)[source]¶
Deprecated: Use
frobenius_polynomial(algorithm="cardinalities")instead. See upstream Issue #40528 for details.
- frobenius_polynomial_matrix(*args, **kwds)[source]¶
Deprecated: Use
frobenius_polynomial(algorithm="matrix")instead. See upstream Issue #40528 for details.
- frobenius_polynomial_pari(*args, **kwds)[source]¶
Deprecated: Use
frobenius_polynomial(algorithm="pari")instead. See upstream Issue #40528 for details.
- p_rank()[source]¶
INPUT:
self– Hyperelliptic Curve of the form \(y^2 = f(x)\) over a finite field, \(\GF{q}\)
OUTPUT: p-rank
EXAMPLES:
sage: K.<x> = GF(49, 'x')[] sage: C = HyperellipticCurve(x^5 + 1, 0) sage: C.p_rank() 0 sage: K.<x> = GF(9, 'x')[] sage: C = HyperellipticCurve(x^7 - 1, 0) sage: C.p_rank() 0 sage: P.<x> = GF(9, 'a')[] sage: E = HyperellipticCurve(x^29 + 1, 0) sage: E.p_rank() 0
>>> from sage.all import * >>> K = GF(Integer(49), 'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(5) + Integer(1), Integer(0)) >>> C.p_rank() 0 >>> K = GF(Integer(9), 'x')['x']; (x,) = K._first_ngens(1) >>> C = HyperellipticCurve(x**Integer(7) - Integer(1), Integer(0)) >>> C.p_rank() 0 >>> P = GF(Integer(9), 'a')['x']; (x,) = P._first_ngens(1) >>> E = HyperellipticCurve(x**Integer(29) + Integer(1), Integer(0)) >>> E.p_rank() 0
K.<x> = GF(49, 'x')[] C = HyperellipticCurve(x^5 + 1, 0) C.p_rank() K.<x> = GF(9, 'x')[] C = HyperellipticCurve(x^7 - 1, 0) C.p_rank() P.<x> = GF(9, 'a')[] E = HyperellipticCurve(x^29 + 1, 0) E.p_rank()
- points()[source]¶
All the points on this hyperelliptic curve.
EXAMPLES:
sage: x = polygen(GF(7)) sage: C = HyperellipticCurve(x^7 - x^2 - 1) sage: C.points() [(0 : 1 : 0), (2 : 5 : 1), (2 : 2 : 1), (3 : 0 : 1), (4 : 6 : 1), (4 : 1 : 1), (5 : 0 : 1), (6 : 5 : 1), (6 : 2 : 1)]
>>> from sage.all import * >>> x = polygen(GF(Integer(7))) >>> C = HyperellipticCurve(x**Integer(7) - x**Integer(2) - Integer(1)) >>> C.points() [(0 : 1 : 0), (2 : 5 : 1), (2 : 2 : 1), (3 : 0 : 1), (4 : 6 : 1), (4 : 1 : 1), (5 : 0 : 1), (6 : 5 : 1), (6 : 2 : 1)]
x = polygen(GF(7)) C = HyperellipticCurve(x^7 - x^2 - 1) C.points()
sage: x = polygen(GF(121, 'a')) sage: C = HyperellipticCurve(x^5 + x - 1, x^2 + 2) sage: len(C.points()) 122
>>> from sage.all import * >>> x = polygen(GF(Integer(121), 'a')) >>> C = HyperellipticCurve(x**Integer(5) + x - Integer(1), x**Integer(2) + Integer(2)) >>> len(C.points()) 122
x = polygen(GF(121, 'a')) C = HyperellipticCurve(x^5 + x - 1, x^2 + 2) len(C.points())
Conics are allowed (the issue reported at upstream Issue #11800 has been resolved):
sage: R.<x> = GF(7)[] sage: H = HyperellipticCurve(3*x^2 + 5*x + 1) sage: H.points() [(0 : 6 : 1), (0 : 1 : 1), (1 : 4 : 1), (1 : 3 : 1), (2 : 4 : 1), (2 : 3 : 1), (3 : 6 : 1), (3 : 1 : 1)]
>>> from sage.all import * >>> R = GF(Integer(7))['x']; (x,) = R._first_ngens(1) >>> H = HyperellipticCurve(Integer(3)*x**Integer(2) + Integer(5)*x + Integer(1)) >>> H.points() [(0 : 6 : 1), (0 : 1 : 1), (1 : 4 : 1), (1 : 3 : 1), (2 : 4 : 1), (2 : 3 : 1), (3 : 6 : 1), (3 : 1 : 1)]
R.<x> = GF(7)[] H = HyperellipticCurve(3*x^2 + 5*x + 1) H.points()
The method currently lists points on the plane projective model, that is the closure in \(\mathbb{P}^2\) of the curve defined by \(y^2+hy=f\). This means that one point \((0:1:0)\) at infinity is returned if the degree of the curve is at least 4 and \(\deg(f)>\deg(h)+1\). This point is a singular point of the plane model. Later implementations may consider a smooth model instead since that would be a more relevant object. Then, for a curve whose only singularity is at \((0:1:0)\), the point at infinity would be replaced by a number of rational points of the smooth model. We illustrate this with an example of a genus 2 hyperelliptic curve:
sage: R.<x>=GF(11)[] sage: H = HyperellipticCurve(x*(x+1)*(x+2)*(x+3)*(x+4)*(x+5)) sage: H.points() [(0 : 1 : 0), (0 : 0 : 1), (1 : 7 : 1), (1 : 4 : 1), (5 : 7 : 1), (5 : 4 : 1), (6 : 0 : 1), (7 : 0 : 1), (8 : 0 : 1), (9 : 0 : 1), (10 : 0 : 1)]
>>> from sage.all import * >>> R = GF(Integer(11))['x']; (x,) = R._first_ngens(1) >>> H = HyperellipticCurve(x*(x+Integer(1))*(x+Integer(2))*(x+Integer(3))*(x+Integer(4))*(x+Integer(5))) >>> H.points() [(0 : 1 : 0), (0 : 0 : 1), (1 : 7 : 1), (1 : 4 : 1), (5 : 7 : 1), (5 : 4 : 1), (6 : 0 : 1), (7 : 0 : 1), (8 : 0 : 1), (9 : 0 : 1), (10 : 0 : 1)]
R.<x>=GF(11)[] H = HyperellipticCurve(x*(x+1)*(x+2)*(x+3)*(x+4)*(x+5)) H.points()
The plane model of the genus 2 hyperelliptic curve in the above example is the curve in \(\mathbb{P}^2\) defined by \(y^2z^4=g(x,z)\) where \(g(x,z)=x(x+z)(x+2z)(x+3z)(x+4z)(x+5z).\) This model has one point at infinity \((0:1:0)\) which is also the only singular point of the plane model. In contrast, the hyperelliptic curve is smooth and imbeds via the equation \(y^2=g(x,z)\) into weighted projected space \(\mathbb{P}(1,3,1)\). The latter model has two points at infinity: \((1:1:0)\) and \((1:-1:0)\).
- zeta_function()[source]¶
Compute the zeta function of the hyperelliptic curve.
EXAMPLES:
sage: F = GF(2); R.<t> = F[] sage: H = HyperellipticCurve(t^9 + t, t^4) sage: H.zeta_function() (16*x^8 + 8*x^7 + 8*x^6 + 4*x^5 + 6*x^4 + 2*x^3 + 2*x^2 + x + 1)/(2*x^2 - 3*x + 1) sage: F.<a> = GF(4); R.<t> = F[] sage: H = HyperellipticCurve(t^5 + t^3 + t^2 + t + 1, t^2 + t + 1) sage: H.zeta_function() (16*x^4 + 8*x^3 + x^2 + 2*x + 1)/(4*x^2 - 5*x + 1) sage: F.<a> = GF(9); R.<t> = F[] sage: H = HyperellipticCurve(t^5 + a*t) sage: H.zeta_function() (81*x^4 + 72*x^3 + 32*x^2 + 8*x + 1)/(9*x^2 - 10*x + 1) sage: R.<t> = PolynomialRing(GF(37)) sage: H = HyperellipticCurve(t^5 + t + 2) sage: H.zeta_function() # needs sage.libs.ntl sage.libs.linbox (1369*x^4 + 37*x^3 - 52*x^2 + x + 1)/(37*x^2 - 38*x + 1)
>>> from sage.all import * >>> F = GF(Integer(2)); R = F['t']; (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(9) + t, t**Integer(4)) >>> H.zeta_function() (16*x^8 + 8*x^7 + 8*x^6 + 4*x^5 + 6*x^4 + 2*x^3 + 2*x^2 + x + 1)/(2*x^2 - 3*x + 1) >>> F = GF(Integer(4), names=('a',)); (a,) = F._first_ngens(1); R = F['t']; (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + t**Integer(3) + t**Integer(2) + t + Integer(1), t**Integer(2) + t + Integer(1)) >>> H.zeta_function() (16*x^4 + 8*x^3 + x^2 + 2*x + 1)/(4*x^2 - 5*x + 1) >>> F = GF(Integer(9), names=('a',)); (a,) = F._first_ngens(1); R = F['t']; (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + a*t) >>> H.zeta_function() (81*x^4 + 72*x^3 + 32*x^2 + 8*x + 1)/(9*x^2 - 10*x + 1) >>> R = PolynomialRing(GF(Integer(37)), names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(t**Integer(5) + t + Integer(2)) >>> H.zeta_function() # needs sage.libs.ntl sage.libs.linbox (1369*x^4 + 37*x^3 - 52*x^2 + x + 1)/(37*x^2 - 38*x + 1)
F = GF(2); R.<t> = F[] H = HyperellipticCurve(t^9 + t, t^4) H.zeta_function() F.<a> = GF(4); R.<t> = F[] H = HyperellipticCurve(t^5 + t^3 + t^2 + t + 1, t^2 + t + 1) H.zeta_function() F.<a> = GF(9); R.<t> = F[] H = HyperellipticCurve(t^5 + a*t) H.zeta_function() R.<t> = PolynomialRing(GF(37)) H = HyperellipticCurve(t^5 + t + 2) H.zeta_function() # needs sage.libs.ntl sage.libs.linbox
A quadratic twist:
sage: R.<t> = PolynomialRing(GF(37)) sage: H = HyperellipticCurve(2*t^5 + 2*t + 4) sage: H.zeta_function() # needs sage.libs.ntl sage.libs.linbox (1369*x^4 - 37*x^3 - 52*x^2 - x + 1)/(37*x^2 - 38*x + 1)
>>> from sage.all import * >>> R = PolynomialRing(GF(Integer(37)), names=('t',)); (t,) = R._first_ngens(1) >>> H = HyperellipticCurve(Integer(2)*t**Integer(5) + Integer(2)*t + Integer(4)) >>> H.zeta_function() # needs sage.libs.ntl sage.libs.linbox (1369*x^4 - 37*x^3 - 52*x^2 - x + 1)/(37*x^2 - 38*x + 1)
R.<t> = PolynomialRing(GF(37)) H = HyperellipticCurve(2*t^5 + 2*t + 4) H.zeta_function() # needs sage.libs.ntl sage.libs.linbox