Jacobian ‘morphism’ as a class in the Picard group

This module implements the group operation in the Picard group of a hyperelliptic curve, represented as divisors in Mumford representation, using Cantor’s algorithm.

A divisor on the hyperelliptic curve \(y^2 + y h(x) = f(x)\) is stored in Mumford representation, that is, as two polynomials \(u(x)\) and \(v(x)\) such that:

  • \(u(x)\) is monic,

  • \(u(x)\) divides \(f(x) - h(x) v(x) - v(x)^2\),

  • \(deg(v(x)) < deg(u(x)) \le g\).

REFERENCES:

A readable introduction to divisors, the Picard group, Mumford representation, and Cantor’s algorithm:

  • J. Scholten, F. Vercauteren. An Introduction to Elliptic and Hyperelliptic Curve Cryptography and the NTRU Cryptosystem. To appear in B. Preneel (Ed.) State of the Art in Applied Cryptography - COSIC ‘03, Lecture Notes in Computer Science, Springer 2004.

A standard reference in the field of cryptography:

  • R. Avanzi, H. Cohen, C. Doche, G. Frey, T. Lange, K. Nguyen, and F. Vercauteren, Handbook of Elliptic and Hyperelliptic Curve Cryptography. CRC Press, 2005.

EXAMPLES: The following curve is the reduction of a curve whose Jacobian has complex multiplication.

sage: x = GF(37)['x'].gen()
sage: H = HyperellipticCurve(x^5 + 12*x^4 + 13*x^3 + 15*x^2 + 33*x); H
Hyperelliptic Curve over Finite Field of size 37 defined
 by y^2 = x^5 + 12*x^4 + 13*x^3 + 15*x^2 + 33*x

>>> from sage.all import *
>>> x = GF(Integer(37))['x'].gen()
>>> H = HyperellipticCurve(x**Integer(5) + Integer(12)*x**Integer(4) + Integer(13)*x**Integer(3) + Integer(15)*x**Integer(2) + Integer(33)*x); H
Hyperelliptic Curve over Finite Field of size 37 defined
 by y^2 = x^5 + 12*x^4 + 13*x^3 + 15*x^2 + 33*x

At this time, Jacobians of hyperelliptic curves are handled differently than elliptic curves:

sage: J = H.jacobian(); J
Jacobian of Hyperelliptic Curve over Finite Field of size 37 defined
 by y^2 = x^5 + 12*x^4 + 13*x^3 + 15*x^2 + 33*x
sage: J = J(J.base_ring()); J
Set of rational points of Jacobian of Hyperelliptic Curve over Finite Field
 of size 37 defined by y^2 = x^5 + 12*x^4 + 13*x^3 + 15*x^2 + 33*x

>>> from sage.all import *
>>> J = H.jacobian(); J
Jacobian of Hyperelliptic Curve over Finite Field of size 37 defined
 by y^2 = x^5 + 12*x^4 + 13*x^3 + 15*x^2 + 33*x
>>> J = J(J.base_ring()); J
Set of rational points of Jacobian of Hyperelliptic Curve over Finite Field
 of size 37 defined by y^2 = x^5 + 12*x^4 + 13*x^3 + 15*x^2 + 33*x

Points on the Jacobian are represented by Mumford’s polynomials. First we find a couple of points on the curve:

sage: P1 = H.lift_x(2); P1
(2 : 11 : 1)
sage: Q1 = H.lift_x(10); Q1
(10 : 18 : 1)

>>> from sage.all import *
>>> P1 = H.lift_x(Integer(2)); P1
(2 : 11 : 1)
>>> Q1 = H.lift_x(Integer(10)); Q1
(10 : 18 : 1)

Observe that 2 and 10 are the roots of the polynomials in x, respectively:

sage: P = J(P1); P
(x + 35, y + 26)
sage: Q = J(Q1); Q
(x + 27, y + 19)

>>> from sage.all import *
>>> P = J(P1); P
(x + 35, y + 26)
>>> Q = J(Q1); Q
(x + 27, y + 19)


sage: P + Q
(x^2 + 25*x + 20, y + 13*x)
sage: (x^2 + 25*x + 20).roots(multiplicities=False)
[10, 2]

>>> from sage.all import *
>>> P + Q
(x^2 + 25*x + 20, y + 13*x)
>>> (x**Integer(2) + Integer(25)*x + Integer(20)).roots(multiplicities=False)
[10, 2]

Frobenius satisfies

\[x^4 + 12*x^3 + 78*x^2 + 444*x + 1369\]

on the Jacobian of this reduction and the order of the Jacobian is \(N = 1904\).

sage: 1904*P
(1)
sage: 34*P == 0
True
sage: 35*P == P
True
sage: 33*P == -P
True

>>> from sage.all import *
>>> Integer(1904)*P
(1)
>>> Integer(34)*P == Integer(0)
True
>>> Integer(35)*P == P
True
>>> Integer(33)*P == -P
True


sage: Q*1904
(1)
sage: Q*238 == 0
True
sage: Q*239 == Q
True
sage: Q*237 == -Q
True

>>> from sage.all import *
>>> Q*Integer(1904)
(1)
>>> Q*Integer(238) == Integer(0)
True
>>> Q*Integer(239) == Q
True
>>> Q*Integer(237) == -Q
True
class sage.schemes.hyperelliptic_curves.jacobian_morphism.JacobianMorphism_divisor_class_field(parent, polys, check=True)[source]

Bases: AdditiveGroupElement, SchemeMorphism

An element of a Jacobian defined over a field, i.e. in \(J(K) = \mathrm{Pic}^0_K(C)\).

point_of_jacobian_of_curve()[source]

Return the point in the Jacobian of the curve.

The Jacobian is the one attached to the projective curve corresponding to this hyperelliptic curve.

EXAMPLES:

sage: R.<x> = PolynomialRing(GF(11))
sage: f = x^6 + x + 1
sage: H = HyperellipticCurve(f)
sage: J = H.jacobian()
sage: D = J(H.lift_x(1))
sage: D  # divisor in Mumford representation
(x + 10, y + 6)
sage: jacobian_order = sum(H.frobenius_polynomial())
sage: jacobian_order
234
sage: p = D.point_of_jacobian_of_curve(); p
[Place (1/x0, 1/x0^3*x1 + 1)
 + Place (x0 + 10, x1 + 6)]
sage: p  # Jacobian point represented by an effective divisor
[Place (1/x0, 1/x0^3*x1 + 1)
 + Place (x0 + 10, x1 + 6)]
sage: p.order()
39
sage: 234*p == 0
True
sage: G = p.parent()
sage: G
Group of rational points of Jacobian over Finite Field of size 11 (Hess model)
sage: J = G.parent()
sage: J
Jacobian of Projective Plane Curve over Finite Field of size 11
 defined by x0^6 + x0^5*x1 + x1^6 - x0^4*x2^2 (Hess model)
sage: C = J.curve()
sage: C
Projective Plane Curve over Finite Field of size 11
 defined by x0^6 + x0^5*x1 + x1^6 - x0^4*x2^2
sage: C.affine_patch(0) == H.affine_patch(2)
True

>>> from sage.all import *
>>> R = PolynomialRing(GF(Integer(11)), names=('x',)); (x,) = R._first_ngens(1)
>>> f = x**Integer(6) + x + Integer(1)
>>> H = HyperellipticCurve(f)
>>> J = H.jacobian()
>>> D = J(H.lift_x(Integer(1)))
>>> D  # divisor in Mumford representation
(x + 10, y + 6)
>>> jacobian_order = sum(H.frobenius_polynomial())
>>> jacobian_order
234
>>> p = D.point_of_jacobian_of_curve(); p
[Place (1/x0, 1/x0^3*x1 + 1)
 + Place (x0 + 10, x1 + 6)]
>>> p  # Jacobian point represented by an effective divisor
[Place (1/x0, 1/x0^3*x1 + 1)
 + Place (x0 + 10, x1 + 6)]
>>> p.order()
39
>>> Integer(234)*p == Integer(0)
True
>>> G = p.parent()
>>> G
Group of rational points of Jacobian over Finite Field of size 11 (Hess model)
>>> J = G.parent()
>>> J
Jacobian of Projective Plane Curve over Finite Field of size 11
 defined by x0^6 + x0^5*x1 + x1^6 - x0^4*x2^2 (Hess model)
>>> C = J.curve()
>>> C
Projective Plane Curve over Finite Field of size 11
 defined by x0^6 + x0^5*x1 + x1^6 - x0^4*x2^2
>>> C.affine_patch(Integer(0)) == H.affine_patch(Integer(2))
True
scheme()[source]

Return the scheme this morphism maps to; or, where this divisor lives.

Warning

Although a pointset is defined over a specific field, the scheme returned may be over a different (usually smaller) field. The example below demonstrates this: the pointset is determined over a number field of absolute degree 2 but the scheme returned is defined over the rationals.

EXAMPLES:

sage: # needs sage.rings.number_field
sage: x = QQ['x'].gen()
sage: f = x^5 + x
sage: H = HyperellipticCurve(f)
sage: F.<a> = NumberField(x^2 - 2, 'a')
sage: J = H.jacobian()(F); J
Set of rational points of Jacobian of Hyperelliptic Curve
 over Number Field in a with defining polynomial x^2 - 2
 defined by y^2 = x^5 + x
sage: P = J(H.lift_x(F(1)))
sage: P.scheme()
Jacobian of Hyperelliptic Curve over Rational Field defined by y^2 = x^5 + x

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> x = QQ['x'].gen()
>>> f = x**Integer(5) + x
>>> H = HyperellipticCurve(f)
>>> F = NumberField(x**Integer(2) - Integer(2), 'a', names=('a',)); (a,) = F._first_ngens(1)
>>> J = H.jacobian()(F); J
Set of rational points of Jacobian of Hyperelliptic Curve
 over Number Field in a with defining polynomial x^2 - 2
 defined by y^2 = x^5 + x
>>> P = J(H.lift_x(F(Integer(1))))
>>> P.scheme()
Jacobian of Hyperelliptic Curve over Rational Field defined by y^2 = x^5 + x
sage.schemes.hyperelliptic_curves.jacobian_morphism.cantor_composition(D1, D2, f, h, genus)[source]

EXAMPLES:

sage: # needs sage.rings.finite_rings
sage: F.<a> = GF(7^2, 'a')
sage: x = F['x'].gen()
sage: f = x^7 + x^2 + a
sage: H = HyperellipticCurve(f, 2*x); H
Hyperelliptic Curve over Finite Field in a of size 7^2
 defined by y^2 + 2*x*y = x^7 + x^2 + a
sage: J = H.jacobian()(F); J
Set of rational points of Jacobian of Hyperelliptic Curve over
 Finite Field in a of size 7^2 defined by y^2 + 2*x*y = x^7 + x^2 + a

>>> from sage.all import *
>>> # needs sage.rings.finite_rings
>>> F = GF(Integer(7)**Integer(2), 'a', names=('a',)); (a,) = F._first_ngens(1)
>>> x = F['x'].gen()
>>> f = x**Integer(7) + x**Integer(2) + a
>>> H = HyperellipticCurve(f, Integer(2)*x); H
Hyperelliptic Curve over Finite Field in a of size 7^2
 defined by y^2 + 2*x*y = x^7 + x^2 + a
>>> J = H.jacobian()(F); J
Set of rational points of Jacobian of Hyperelliptic Curve over
 Finite Field in a of size 7^2 defined by y^2 + 2*x*y = x^7 + x^2 + a


sage: Q = J(H.lift_x(F(1))); Q                                                  # needs sage.rings.finite_rings
(x + 6, y + 5*a)
sage: 10*Q  # indirect doctest                                                  # needs sage.rings.finite_rings
(x^3 + (3*a + 1)*x^2 + (2*a + 5)*x + a + 5, y + (3*a + 2)*x^2 + (6*a + 1)*x + a + 4)
sage: 7*8297*Q                                                                  # needs sage.rings.finite_rings
(1)

>>> from sage.all import *
>>> Q = J(H.lift_x(F(Integer(1)))); Q                                                  # needs sage.rings.finite_rings
(x + 6, y + 5*a)
>>> Integer(10)*Q  # indirect doctest                                                  # needs sage.rings.finite_rings
(x^3 + (3*a + 1)*x^2 + (2*a + 5)*x + a + 5, y + (3*a + 2)*x^2 + (6*a + 1)*x + a + 4)
>>> Integer(7)*Integer(8297)*Q                                                                  # needs sage.rings.finite_rings
(1)


sage: Q = J(H.lift_x(F(a+1))); Q                                                # needs sage.rings.finite_rings
(x + 6*a + 6, y + 2)
sage: 7*8297*Q  # indirect doctest                                              # needs sage.rings.finite_rings
(1)

A test over a prime field:

sage: # needs sage.rings.finite_rings
sage: F = GF(next_prime(10^30))
sage: x = F['x'].gen()
sage: f = x^7 + x^2 + 1
sage: H = HyperellipticCurve(f, 2*x); H
Hyperelliptic Curve over Finite Field of size 1000000000000000000000000000057
 defined by y^2 + 2*x*y = x^7 + x^2 + 1
sage: J = H.jacobian()(F); J
Set of rational points of Jacobian of Hyperelliptic Curve
 over Finite Field of size 1000000000000000000000000000057
 defined by y^2 + 2*x*y = x^7 + x^2 + 1
sage: Q = J(H.lift_x(F(1))); Q
(x + 1000000000000000000000000000056, y + 1000000000000000000000000000056)
sage: 10*Q  # indirect doctest
(x^3 + 150296037169838934997145567227*x^2
     + 377701248971234560956743242408*x + 509456150352486043408603286615,
 y + 514451014495791237681619598519*x^2
   + 875375621665039398768235387900*x + 861429240012590886251910326876)
sage: 7*8297*Q
(x^3 + 35410976139548567549919839063*x^2
     + 26230404235226464545886889960*x + 681571430588959705539385624700,
 y + 999722365017286747841221441793*x^2
   + 262703715994522725686603955650*x + 626219823403254233972118260890)

>>> from sage.all import *
>>> Q = J(H.lift_x(F(a+Integer(1)))); Q                                                # needs sage.rings.finite_rings
(x + 6*a + 6, y + 2)
>>> Integer(7)*Integer(8297)*Q  # indirect doctest                                              # needs sage.rings.finite_rings
(1)

A test over a prime field:

>>> # needs sage.rings.finite_rings
>>> F = GF(next_prime(Integer(10)**Integer(30)))
>>> x = F['x'].gen()
>>> f = x**Integer(7) + x**Integer(2) + Integer(1)
>>> H = HyperellipticCurve(f, Integer(2)*x); H
Hyperelliptic Curve over Finite Field of size 1000000000000000000000000000057
 defined by y^2 + 2*x*y = x^7 + x^2 + 1
>>> J = H.jacobian()(F); J
Set of rational points of Jacobian of Hyperelliptic Curve
 over Finite Field of size 1000000000000000000000000000057
 defined by y^2 + 2*x*y = x^7 + x^2 + 1
>>> Q = J(H.lift_x(F(Integer(1)))); Q
(x + 1000000000000000000000000000056, y + 1000000000000000000000000000056)
>>> Integer(10)*Q  # indirect doctest
(x^3 + 150296037169838934997145567227*x^2
     + 377701248971234560956743242408*x + 509456150352486043408603286615,
 y + 514451014495791237681619598519*x^2
   + 875375621665039398768235387900*x + 861429240012590886251910326876)
>>> Integer(7)*Integer(8297)*Q
(x^3 + 35410976139548567549919839063*x^2
     + 26230404235226464545886889960*x + 681571430588959705539385624700,
 y + 999722365017286747841221441793*x^2
   + 262703715994522725686603955650*x + 626219823403254233972118260890)
sage.schemes.hyperelliptic_curves.jacobian_morphism.cantor_composition_simple(D1, D2, f, genus)[source]

Given \(D_1\) and \(D_2\) two reduced Mumford divisors on the Jacobian of the curve \(y^2 = f(x)\), computes a representative \(D_1 + D_2\).

Warning

The representative computed is NOT reduced! Use cantor_reduction_simple() to reduce it.

EXAMPLES:

sage: x = QQ['x'].gen()
sage: f = x^5 + x
sage: H = HyperellipticCurve(f); H
Hyperelliptic Curve over Rational Field defined by y^2 = x^5 + x

>>> from sage.all import *
>>> x = QQ['x'].gen()
>>> f = x**Integer(5) + x
>>> H = HyperellipticCurve(f); H
Hyperelliptic Curve over Rational Field defined by y^2 = x^5 + x


sage: F.<a> = NumberField(x^2 - 2, 'a')                                         # needs sage.rings.number_field
sage: J = H.jacobian()(F); J                                                    # needs sage.rings.number_field
Set of rational points of Jacobian of Hyperelliptic Curve over
 Number Field in a with defining polynomial x^2 - 2 defined by y^2 = x^5 + x

>>> from sage.all import *
>>> F = NumberField(x**Integer(2) - Integer(2), 'a', names=('a',)); (a,) = F._first_ngens(1)# needs sage.rings.number_field
>>> J = H.jacobian()(F); J                                                    # needs sage.rings.number_field
Set of rational points of Jacobian of Hyperelliptic Curve over
 Number Field in a with defining polynomial x^2 - 2 defined by y^2 = x^5 + x


sage: # needs sage.rings.number_field
sage: P = J(H.lift_x(F(1))); P
(x - 1, y + a)
sage: Q = J(H.lift_x(F(0))); Q
(x, y)
sage: 2*P + 2*Q # indirect doctest
(x^2 - 2*x + 1, y + 3/2*a*x - 1/2*a)
sage: 2*(P + Q) # indirect doctest
(x^2 - 2*x + 1, y + 3/2*a*x - 1/2*a)
sage: 3*P # indirect doctest
(x^2 - 25/32*x + 49/32, y + 45/256*a*x + 315/256*a)

>>> from sage.all import *
>>> # needs sage.rings.number_field
>>> P = J(H.lift_x(F(Integer(1)))); P
(x - 1, y + a)
>>> Q = J(H.lift_x(F(Integer(0)))); Q
(x, y)
>>> Integer(2)*P + Integer(2)*Q # indirect doctest
(x^2 - 2*x + 1, y + 3/2*a*x - 1/2*a)
>>> Integer(2)*(P + Q) # indirect doctest
(x^2 - 2*x + 1, y + 3/2*a*x - 1/2*a)
>>> Integer(3)*P # indirect doctest
(x^2 - 25/32*x + 49/32, y + 45/256*a*x + 315/256*a)
sage.schemes.hyperelliptic_curves.jacobian_morphism.cantor_reduction(a, b, f, h, genus)[source]

Return the unique reduced divisor linearly equivalent to \((a, b)\) on the curve \(y^2 + y h(x) = f(x)\).

See the docstring of sage.schemes.hyperelliptic_curves.jacobian_morphism for information about divisors, linear equivalence, and reduction.

EXAMPLES:

sage: x = QQ['x'].gen()
sage: f = x^5 - x
sage: H = HyperellipticCurve(f, x); H
Hyperelliptic Curve over Rational Field defined by y^2 + x*y = x^5 - x
sage: J = H.jacobian()(QQ); J
Set of rational points of Jacobian of Hyperelliptic Curve over
 Rational Field defined by y^2 + x*y = x^5 - x

>>> from sage.all import *
>>> x = QQ['x'].gen()
>>> f = x**Integer(5) - x
>>> H = HyperellipticCurve(f, x); H
Hyperelliptic Curve over Rational Field defined by y^2 + x*y = x^5 - x
>>> J = H.jacobian()(QQ); J
Set of rational points of Jacobian of Hyperelliptic Curve over
 Rational Field defined by y^2 + x*y = x^5 - x

The following point is 2-torsion:

sage: Q = J(H.lift_x(0)); Q
(x, y)
sage: 2*Q # indirect doctest
(1)

>>> from sage.all import *
>>> Q = J(H.lift_x(Integer(0))); Q
(x, y)
>>> Integer(2)*Q # indirect doctest
(1)

The next point is not 2-torsion:

sage: P = J(H.lift_x(-1)); P
(x + 1, y)
sage: 2 * J(H.lift_x(-1)) # indirect doctest
(x^2 + 2*x + 1, y + 4*x + 4)
sage: 3 * J(H.lift_x(-1)) # indirect doctest
(x^2 - 487*x - 324, y + 10755*x + 7146)

>>> from sage.all import *
>>> P = J(H.lift_x(-Integer(1))); P
(x + 1, y)
>>> Integer(2) * J(H.lift_x(-Integer(1))) # indirect doctest
(x^2 + 2*x + 1, y + 4*x + 4)
>>> Integer(3) * J(H.lift_x(-Integer(1))) # indirect doctest
(x^2 - 487*x - 324, y + 10755*x + 7146)
sage.schemes.hyperelliptic_curves.jacobian_morphism.cantor_reduction_simple(a, b, f, genus)[source]

Return the unique reduced divisor linearly equivalent to \((a, b)\) on the curve \(y^2 = f(x).\)

See the docstring of sage.schemes.hyperelliptic_curves.jacobian_morphism for information about divisors, linear equivalence, and reduction.

EXAMPLES:

sage: x = QQ['x'].gen()
sage: f = x^5 - x
sage: H = HyperellipticCurve(f); H
Hyperelliptic Curve over Rational Field defined by y^2 = x^5 - x
sage: J = H.jacobian()(QQ); J
Set of rational points of Jacobian of Hyperelliptic Curve over Rational Field
 defined by y^2 = x^5 - x

>>> from sage.all import *
>>> x = QQ['x'].gen()
>>> f = x**Integer(5) - x
>>> H = HyperellipticCurve(f); H
Hyperelliptic Curve over Rational Field defined by y^2 = x^5 - x
>>> J = H.jacobian()(QQ); J
Set of rational points of Jacobian of Hyperelliptic Curve over Rational Field
 defined by y^2 = x^5 - x

The following point is 2-torsion:

sage: P = J(H.lift_x(-1)); P
(x + 1, y)
sage: 2 * P # indirect doctest
(1)

>>> from sage.all import *
>>> P = J(H.lift_x(-Integer(1))); P
(x + 1, y)
>>> Integer(2) * P # indirect doctest
(1)