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), (2*a : 2*a + 2 : 1), (2*a : 2*a : 1), (a + 1 : a : 1), (a + 1 : a + 1 : 1), (2 : a + 1 : 1), (1 : a + 1 : 1)]
class sage.schemes.hyperelliptic_curves.hyperelliptic_finite_field.HyperellipticCurve_finite_field(PP, f, h=None, names=None, genus=None)
_frobenius_coefficient_bound()

Computes bound on number of p-adic digits needed to recover frobenius polynomial, i.e. returns B so that knowledge of a_1, ..., a_g modulo p^B determine frobenius polynomial uniquely.

TESTS::

sage: R.<t> = PolynomialRing(GF(37)) sage: HyperellipticCurve(t^3 + t + 1)._frobenius_coefficient_bound() 1 sage: HyperellipticCurve(t^5 + t + 1)._frobenius_coefficient_bound() 2 sage: HyperellipticCurve(t^7 + t + 1)._frobenius_coefficient_bound() 3

sage: R.<t> = PolynomialRing(GF(next_prime(10^9))) sage: HyperellipticCurve(t^3 + t + 1)._frobenius_coefficient_bound() 1 sage: HyperellipticCurve(t^5 + t + 1)._frobenius_coefficient_bound() 2 sage: HyperellipticCurve(t^7 + t + 1)._frobenius_coefficient_bound() 2 sage: HyperellipticCurve(t^9 + t + 1)._frobenius_coefficient_bound() 3 sage: HyperellipticCurve(t^11 + t + 1)._frobenius_coefficient_bound() 3 sage: HyperellipticCurve(t^13 + t + 1)._frobenius_coefficient_bound() 4

_frobenius_matrix(N=None)

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.

Currently only implemented using hypellfrob, which means only works over GF(p^1), and must have p > (2g+1)(2N-1).

TESTS::
sage: R.<t> = PolynomialRing(GF(37)) sage: H = HyperellipticCurve(t^5 + t + 2) sage: H._frobenius_matrix() [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)]
_points_cache_sqrt(brute_force=False)

Count points by enumerating over x and solving the resulting quadratic for y.

Caches all square roots ahead of time by squaring every element of the field. Elements must have an __index__ method.

EXAMPLES:

sage: x = polygen(GF(7))
sage: C = HyperellipticCurve(x^3 + x^2 - 1)
sage: C._points_cache_sqrt()
[(0 : 1 : 0), (1 : 6 : 1), (1 : 1 : 1), (2 : 5 : 1), (2 : 2 : 1), (3 : 0 : 1), (4 : 4 : 1), (4 : 3 : 1), (5 : 4 : 1), (5 : 3 : 1)]
sage: set(C._points_cache_sqrt()) == set(C._points_cache_sqrt(brute_force=True))
True
_points_fast_sqrt()

Count points by enumerating over x and solving the resulting quadratic for y.

EXAMPLES:

sage: K.<a> = GF(9, 'a')
sage: x = polygen(K)
sage: C = HyperellipticCurve(x^7 - 1, x^2 + a)
sage: C._points_fast_sqrt()
[(0 : 1 : 0), (2 : a + 1 : 1), (a : 2*a + 1 : 1), (2*a + 2 : 2*a : 1), (2*a + 2 : 1 : 1), (1 : 2*a + 2 : 1), (1 : 0 : 1)]
sage: K.<a> = GF(49, 'a')
sage: x = polygen(K)
sage: C = HyperellipticCurve(x^5 - x^2 - 1, x^2 + a)
sage: len(C._points_fast_sqrt())
31

TESTS:

sage: x = polygen(GF(16, 'a'))
sage: C = HyperellipticCurve(x^5 - x + 1, x^2 + x)
sage: set(C._points_fast_sqrt()) == set(C._points_cache_sqrt())
True
sage: x = polygen(GF(19))
sage: C = HyperellipticCurve(x^5 + 5*x^2 + 1, x + 1)
sage: set(C._points_fast_sqrt()) == set(C._points_cache_sqrt())
True
sage: x = polygen(GF(13))
sage: C = HyperellipticCurve(x^3 + x^2 - 1)
sage: C._points_fast_sqrt()
[(0 : 1 : 0), (0 : 5 : 1), (0 : 8 : 1), (1 : 1 : 1), (1 : 12 : 1), (3 : 3 : 1), (3 : 10 : 1), (4 : 1 : 1), (4 : 12 : 1), (6 : 2 : 1), (6 : 11 : 1), (7 : 1 : 1), (7 : 12 : 1), (8 : 4 : 1), (8 : 9 : 1), (9 : 4 : 1), (9 : 9 : 1), (12 : 5 : 1), (12 : 8 : 1)]
sage: set(C._points_fast_sqrt()) == set(C._points_cache_sqrt())
True
frobenius_polynomial()

Charpoly of frobenius, as an element of ZZ[x].

TESTS::
sage: R.<t> = PolynomialRing(GF(37)) sage: H = HyperellipticCurve(t^5 + t + 2) sage: H.frobenius_polynomial() x^4 + x^3 - 52*x^2 + 37*x + 1369
A quadratic twist:
sage: H = HyperellipticCurve(2*t^5 + 2*t + 4) sage: H.frobenius_polynomial() x^4 - x^3 - 52*x^2 - 37*x + 1369
points()

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)]
sage: x = polygen(GF(121, 'a'))
sage: C = HyperellipticCurve(x^5 + x - 1, x^2 + 2)
sage: len(C.points())
122

Previous topic

Hyperelliptic curve constructor

Next topic

Hyperelliptic curves over a general ring

This Page