Scalar-multiplication morphisms of elliptic curves#

This class provides an EllipticCurveHom instantiation for multiplication-by-\(m\) maps on elliptic curves.

EXAMPLES:

We can construct and evaluate scalar multiplications:

sage: from sage.schemes.elliptic_curves.hom_scalar import EllipticCurveHom_scalar
sage: E = EllipticCurve('77a1')
sage: phi = E.scalar_multiplication(5); phi
Scalar-multiplication endomorphism [5] of Elliptic Curve defined by y^2 + y = x^3 + 2*x over Rational Field
sage: P = E(2,3)
sage: phi(P)
(30 : 164 : 1)

>>> from sage.all import *
>>> from sage.schemes.elliptic_curves.hom_scalar import EllipticCurveHom_scalar
>>> E = EllipticCurve('77a1')
>>> phi = E.scalar_multiplication(Integer(5)); phi
Scalar-multiplication endomorphism [5] of Elliptic Curve defined by y^2 + y = x^3 + 2*x over Rational Field
>>> P = E(Integer(2),Integer(3))
>>> phi(P)
(30 : 164 : 1)

The usual EllipticCurveHom methods are supported:

sage: phi.degree()
25
sage: phi.kernel_polynomial()
x^12 + 124/5*x^10 + 19*x^9 - 84*x^8 + 24*x^7 - 483*x^6 - 696/5*x^5 - 448*x^4 - 37*x^3 - 332*x^2 - 84*x + 47/5
sage: phi.rational_maps()
((x^25 - 200*x^23 - 520*x^22 + 9000*x^21 + ... + 1377010*x^3 + 20360*x^2 - 39480*x + 2209),
 (10*x^36*y - 620*x^36 + 3240*x^34*y - 44880*x^34 + ... + 424927560*x*y + 226380480*x + 42986410*y + 20974090)/(1250*x^36 + 93000*x^34 + 71250*x^33 + 1991400*x^32 + ... + 1212964050*x^3 + 138715800*x^2 - 27833400*x + 1038230))
sage: phi.dual()
Scalar-multiplication endomorphism [5] of Elliptic Curve defined by y^2 + y = x^3 + 2*x over Rational Field
sage: phi.dual() is phi
True
sage: phi.formal()
5*t - 310*t^4 - 2496*t^5 + 10540*t^7 + ... - 38140146674516*t^20 - 46800256902400*t^21 + 522178541079910*t^22 + O(t^23)
sage: phi.is_normalized()
False
sage: phi.is_separable()
True
sage: phi.is_injective()
False
sage: phi.is_surjective()
True

>>> from sage.all import *
>>> phi.degree()
25
>>> phi.kernel_polynomial()
x^12 + 124/5*x^10 + 19*x^9 - 84*x^8 + 24*x^7 - 483*x^6 - 696/5*x^5 - 448*x^4 - 37*x^3 - 332*x^2 - 84*x + 47/5
>>> phi.rational_maps()
((x^25 - 200*x^23 - 520*x^22 + 9000*x^21 + ... + 1377010*x^3 + 20360*x^2 - 39480*x + 2209),
 (10*x^36*y - 620*x^36 + 3240*x^34*y - 44880*x^34 + ... + 424927560*x*y + 226380480*x + 42986410*y + 20974090)/(1250*x^36 + 93000*x^34 + 71250*x^33 + 1991400*x^32 + ... + 1212964050*x^3 + 138715800*x^2 - 27833400*x + 1038230))
>>> phi.dual()
Scalar-multiplication endomorphism [5] of Elliptic Curve defined by y^2 + y = x^3 + 2*x over Rational Field
>>> phi.dual() is phi
True
>>> phi.formal()
5*t - 310*t^4 - 2496*t^5 + 10540*t^7 + ... - 38140146674516*t^20 - 46800256902400*t^21 + 522178541079910*t^22 + O(t^23)
>>> phi.is_normalized()
False
>>> phi.is_separable()
True
>>> phi.is_injective()
False
>>> phi.is_surjective()
True

Contrary to constructing an EllipticCurveIsogeny from the division polynomial, EllipticCurveHom_scalar can deal with huge scalars very quickly:

sage: E = EllipticCurve(GF(2^127-1), [1,2,3,4,5])
sage: phi = E.scalar_multiplication(9^99); phi
Scalar-multiplication endomorphism [29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889] of Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 170141183460469231731687303715884105727
sage: phi(E(1,2))
(82124533143060719620799539030695848450 : 17016022038624814655722682134021402379 : 1)

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(2)**Integer(127)-Integer(1)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> phi = E.scalar_multiplication(Integer(9)**Integer(99)); phi
Scalar-multiplication endomorphism [29512665430652752148753480226197736314359272517043832886063884637676943433478020332709411004889] of Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 170141183460469231731687303715884105727
>>> phi(E(Integer(1),Integer(2)))
(82124533143060719620799539030695848450 : 17016022038624814655722682134021402379 : 1)

Composition of scalar multiplications results in another scalar multiplication:

sage: E = EllipticCurve(GF(19), [4,4])
sage: phi = E.scalar_multiplication(-3); phi
Scalar-multiplication endomorphism [-3] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
sage: psi = E.scalar_multiplication(7); psi
Scalar-multiplication endomorphism [7] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
sage: phi * psi
Scalar-multiplication endomorphism [-21] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
sage: psi * phi
Scalar-multiplication endomorphism [-21] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
sage: phi * psi == psi * phi
True
sage: -phi == E.scalar_multiplication(-1) * phi
True

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(19)), [Integer(4),Integer(4)])
>>> phi = E.scalar_multiplication(-Integer(3)); phi
Scalar-multiplication endomorphism [-3] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
>>> psi = E.scalar_multiplication(Integer(7)); psi
Scalar-multiplication endomorphism [7] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
>>> phi * psi
Scalar-multiplication endomorphism [-21] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
>>> psi * phi
Scalar-multiplication endomorphism [-21] of Elliptic Curve defined by y^2 = x^3 + 4*x + 4 over Finite Field of size 19
>>> phi * psi == psi * phi
True
>>> -phi == E.scalar_multiplication(-Integer(1)) * phi
True

The zero endomorphism \([0]\) is supported:

sage: E = EllipticCurve(GF(71), [1,1])
sage: zero = E.scalar_multiplication(0); zero
Scalar-multiplication endomorphism [0] of Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 71
sage: zero.is_zero()
True
sage: zero.is_injective()
False
sage: zero.is_surjective()
False
sage: zero(E.random_point())
(0 : 1 : 0)

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(71)), [Integer(1),Integer(1)])
>>> zero = E.scalar_multiplication(Integer(0)); zero
Scalar-multiplication endomorphism [0] of Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 71
>>> zero.is_zero()
True
>>> zero.is_injective()
False
>>> zero.is_surjective()
False
>>> zero(E.random_point())
(0 : 1 : 0)

Retrieving multiplication-by-\(m\) maps when \(m\) is divisible by the characteristic also works (since Issue #37096):

sage: E = EllipticCurve(GF(7), [1,0])
sage: phi = E.scalar_multiplication(7); phi
Scalar-multiplication endomorphism [7] of Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7
sage: phi.rational_maps()
(x^49, -y^49)
sage: phi.x_rational_map()
x^49
sage: psi = E.scalar_multiplication(-2); psi
Scalar-multiplication endomorphism [-2] of Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7
sage: chi = E.scalar_multiplication(-14); chi
Scalar-multiplication endomorphism [-14] of Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7
sage: chi == psi * phi
True
sage: chi.rational_maps()
((x^196 - 2*x^98 + 1)/(-3*x^147 - 3*x^49),
 (-x^294*y^49 + 2*x^196*y^49 - 2*x^98*y^49 + y^49)/(-x^294 - 2*x^196 - x^98))
sage: chi.x_rational_map()
(2*x^196 + 3*x^98 + 2)/(x^147 + x^49)
sage: chi.rational_maps() == tuple(f(*phi.rational_maps()) for f in psi.rational_maps())
True
sage: chi.x_rational_map() == psi.x_rational_map()(phi.x_rational_map())
True

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(1),Integer(0)])
>>> phi = E.scalar_multiplication(Integer(7)); phi
Scalar-multiplication endomorphism [7] of Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7
>>> phi.rational_maps()
(x^49, -y^49)
>>> phi.x_rational_map()
x^49
>>> psi = E.scalar_multiplication(-Integer(2)); psi
Scalar-multiplication endomorphism [-2] of Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7
>>> chi = E.scalar_multiplication(-Integer(14)); chi
Scalar-multiplication endomorphism [-14] of Elliptic Curve defined by y^2 = x^3 + x over Finite Field of size 7
>>> chi == psi * phi
True
>>> chi.rational_maps()
((x^196 - 2*x^98 + 1)/(-3*x^147 - 3*x^49),
 (-x^294*y^49 + 2*x^196*y^49 - 2*x^98*y^49 + y^49)/(-x^294 - 2*x^196 - x^98))
>>> chi.x_rational_map()
(2*x^196 + 3*x^98 + 2)/(x^147 + x^49)
>>> chi.rational_maps() == tuple(f(*phi.rational_maps()) for f in psi.rational_maps())
True
>>> chi.x_rational_map() == psi.x_rational_map()(phi.x_rational_map())
True

sage: E = EllipticCurve(GF(7), [0,1])
sage: phi = E.scalar_multiplication(7); phi
Scalar-multiplication endomorphism [7] of Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7
sage: phi.rational_maps()   # known bug -- #6413
((-3*x^49 - x^28 - x^7)/(x^42 - x^21 + 2),
 (-x^72*y - 3*x^69*y - 3*x^66*y - x^63*y + 3*x^51*y + 2*x^48*y + 2*x^45*y + 3*x^42*y - x^9*y - 3*x^6*y - 3*x^3*y - y)/(x^63 + 2*x^42 - x^21 - 1))
sage: phi.x_rational_map()
(4*x^49 + 6*x^28 + 6*x^7)/(x^42 + 6*x^21 + 2)

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(0),Integer(1)])
>>> phi = E.scalar_multiplication(Integer(7)); phi
Scalar-multiplication endomorphism [7] of Elliptic Curve defined by y^2 = x^3 + 1 over Finite Field of size 7
>>> phi.rational_maps()   # known bug -- #6413
((-3*x^49 - x^28 - x^7)/(x^42 - x^21 + 2),
 (-x^72*y - 3*x^69*y - 3*x^66*y - x^63*y + 3*x^51*y + 2*x^48*y + 2*x^45*y + 3*x^42*y - x^9*y - 3*x^6*y - 3*x^3*y - y)/(x^63 + 2*x^42 - x^21 - 1))
>>> phi.x_rational_map()
(4*x^49 + 6*x^28 + 6*x^7)/(x^42 + 6*x^21 + 2)

AUTHORS:

class sage.schemes.elliptic_curves.hom_scalar.EllipticCurveHom_scalar(E, m)[source]#

Bases: EllipticCurveHom

Construct a scalar-multiplication map on an elliptic curve.

degree()[source]#

Return the degree of this scalar-multiplication morphism.

The map \([m]\) has degree \(m^2\).

EXAMPLES:

sage: E = EllipticCurve(GF(23), [0,1])
sage: phi = E.scalar_multiplication(1111111)
sage: phi.degree()
1234567654321

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(23)), [Integer(0),Integer(1)])
>>> phi = E.scalar_multiplication(Integer(1111111))
>>> phi.degree()
1234567654321
dual()[source]#

Return the dual isogeny of this scalar-multiplication map.

This method simply returns self as scalars are self-dual.

EXAMPLES:

sage: E = EllipticCurve([5,5])
sage: phi = E.scalar_multiplication(5)
sage: phi.dual() is phi
True

>>> from sage.all import *
>>> E = EllipticCurve([Integer(5),Integer(5)])
>>> phi = E.scalar_multiplication(Integer(5))
>>> phi.dual() is phi
True
inseparable_degree()[source]#

Return the inseparable degree of this scalar-multiplication map.

EXAMPLES:

sage: E = EllipticCurve(GF(7), [0,1])
sage: E.is_supersingular()
False
sage: E.scalar_multiplication(4).inseparable_degree()
1
sage: E.scalar_multiplication(-7).inseparable_degree()
7

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(0),Integer(1)])
>>> E.is_supersingular()
False
>>> E.scalar_multiplication(Integer(4)).inseparable_degree()
1
>>> E.scalar_multiplication(-Integer(7)).inseparable_degree()
7

sage: E = EllipticCurve(GF(7), [1,0])
sage: E.is_supersingular()
True
sage: E.scalar_multiplication(4).inseparable_degree()
1
sage: E.scalar_multiplication(-7).inseparable_degree()
49

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(7)), [Integer(1),Integer(0)])
>>> E.is_supersingular()
True
>>> E.scalar_multiplication(Integer(4)).inseparable_degree()
1
>>> E.scalar_multiplication(-Integer(7)).inseparable_degree()
49
kernel_polynomial()[source]#

Return the kernel polynomial of this scalar-multiplication map. (When \(m=0\), return \(0\).)

EXAMPLES:

sage: E = EllipticCurve(GF(997), [7,7,7,7,7])
sage: phi = E.scalar_multiplication(5)
sage: phi.kernel_polynomial()
x^12 + 77*x^11 + 380*x^10 + 198*x^9 + 840*x^8 + 376*x^7 + 946*x^6 + 848*x^5 + 246*x^4 + 778*x^3 + 77*x^2 + 518*x + 28

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(997)), [Integer(7),Integer(7),Integer(7),Integer(7),Integer(7)])
>>> phi = E.scalar_multiplication(Integer(5))
>>> phi.kernel_polynomial()
x^12 + 77*x^11 + 380*x^10 + 198*x^9 + 840*x^8 + 376*x^7 + 946*x^6 + 848*x^5 + 246*x^4 + 778*x^3 + 77*x^2 + 518*x + 28

sage: E = EllipticCurve(GF(997), [5,6,7,8,9])
sage: phi = E.scalar_multiplication(11)
sage: phi.kernel_polynomial()
x^60 + 245*x^59 + 353*x^58 + 693*x^57 + 499*x^56 + 462*x^55 + 820*x^54 + 962*x^53 + ... + 736*x^7 + 939*x^6 + 429*x^5 + 267*x^4 + 116*x^3 + 770*x^2 + 491*x + 519

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(997)), [Integer(5),Integer(6),Integer(7),Integer(8),Integer(9)])
>>> phi = E.scalar_multiplication(Integer(11))
>>> phi.kernel_polynomial()
x^60 + 245*x^59 + 353*x^58 + 693*x^57 + 499*x^56 + 462*x^55 + 820*x^54 + 962*x^53 + ... + 736*x^7 + 939*x^6 + 429*x^5 + 267*x^4 + 116*x^3 + 770*x^2 + 491*x + 519
rational_maps()[source]#

Return the pair of explicit rational maps defining this scalar multiplication.

ALGORITHM: EllipticCurve_generic.multiplication_by_m()

EXAMPLES:

sage: E = EllipticCurve('77a1')
sage: phi = E.scalar_multiplication(5)
sage: phi.rational_maps()
((x^25 - 200*x^23 - 520*x^22 + ... + 368660*x^2 + 163195*x + 16456)/(25*x^24 + 1240*x^22 + 950*x^21 + ... + 20360*x^2 - 39480*x + 2209),
 (10*x^36*y - 620*x^36 + 3240*x^34*y - ... + 226380480*x + 42986410*y + 20974090)/(1250*x^36 + 93000*x^34 + 71250*x^33 + ... + 138715800*x^2 - 27833400*x + 1038230))
sage: P = (2,3)
sage: Q = tuple(r(P) for r in phi.rational_maps()); Q
(30, 164)
sage: E(Q) == 5*E(P)
True

>>> from sage.all import *
>>> E = EllipticCurve('77a1')
>>> phi = E.scalar_multiplication(Integer(5))
>>> phi.rational_maps()
((x^25 - 200*x^23 - 520*x^22 + ... + 368660*x^2 + 163195*x + 16456)/(25*x^24 + 1240*x^22 + 950*x^21 + ... + 20360*x^2 - 39480*x + 2209),
 (10*x^36*y - 620*x^36 + 3240*x^34*y - ... + 226380480*x + 42986410*y + 20974090)/(1250*x^36 + 93000*x^34 + 71250*x^33 + ... + 138715800*x^2 - 27833400*x + 1038230))
>>> P = (Integer(2),Integer(3))
>>> Q = tuple(r(P) for r in phi.rational_maps()); Q
(30, 164)
>>> E(Q) == Integer(5)*E(P)
True
scaling_factor()[source]#

Return the Weierstrass scaling factor associated to this scalar multiplication.

The scaling factor is the constant \(u\) (in the base field) such that \(\varphi^* \omega_2 = u \omega_1\), where \(\varphi: E_1\to E_2\) is this morphism and \(\omega_i\) are the standard Weierstrass differentials on \(E_i\) defined by \(\mathrm dx/(2y+a_1x+a_3)\).

EXAMPLES:

sage: E = EllipticCurve('11a1')
sage: phi = E.scalar_multiplication(5)
sage: u = phi.scaling_factor()
sage: u == phi.formal()[1]
True
sage: u == E.multiplication_by_m_isogeny(5).scaling_factor()
doctest:warning ... DeprecationWarning: ...
True

>>> from sage.all import *
>>> E = EllipticCurve('11a1')
>>> phi = E.scalar_multiplication(Integer(5))
>>> u = phi.scaling_factor()
>>> u == phi.formal()[Integer(1)]
True
>>> u == E.multiplication_by_m_isogeny(Integer(5)).scaling_factor()
doctest:warning ... DeprecationWarning: ...
True

The scaling factor lives in the base ring:

sage: E = EllipticCurve(GF(101^2), [5,5])
sage: phi = E.scalar_multiplication(123)
sage: phi.scaling_factor()
22
sage: phi.scaling_factor().parent()
Finite Field in z2 of size 101^2

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(101)**Integer(2)), [Integer(5),Integer(5)])
>>> phi = E.scalar_multiplication(Integer(123))
>>> phi.scaling_factor()
22
>>> phi.scaling_factor().parent()
Finite Field in z2 of size 101^2

ALGORITHM: The scaling factor equals the scalar that is being multiplied by.

x_rational_map()[source]#

Return the \(x\)-coordinate rational map of this scalar multiplication.

ALGORITHM: EllipticCurve_generic.multiplication_by_m()

EXAMPLES:

sage: E = EllipticCurve(GF(65537), [1,2,3,4,5])
sage: phi = E.scalar_multiplication(7)
sage: phi.x_rational_map() == phi.rational_maps()[0]
True

>>> from sage.all import *
>>> E = EllipticCurve(GF(Integer(65537)), [Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])
>>> phi = E.scalar_multiplication(Integer(7))
>>> phi.x_rational_map() == phi.rational_maps()[Integer(0)]
True