Square‑root Vélu algorithm for elliptic-curve isogenies#
The square-root Vélu algorithm, also called the √élu algorithm, computes isogenies of elliptic curves in time \(\tilde O(\sqrt\ell)\) rather than naïvely \(O(\ell)\), where \(\ell\) is the degree.
The core idea is to reindex the points in the kernel subgroup in a
baby-step-giant-step manner, then use fast resultant computations to evaluate
“elliptic polynomials” (see FastEllipticPolynomial
) in essentially
square-root time.
Based on experiments with Sage version 9.7, the isogeny degree where
EllipticCurveHom_velusqrt
begins to outperform
EllipticCurveIsogeny
can be as low as \(\approx 100\), but is typically closer to \(\approx 1000\),
depending on the exact situation.
REFERENCES: [BDLS2020]
EXAMPLES:
sage: from sage.schemes.elliptic_curves.hom_velusqrt import EllipticCurveHom_velusqrt
sage: E = EllipticCurve(GF(6666679), [5,5])
sage: K = E(9970, 1003793, 1)
sage: K.order()
10009
sage: phi = EllipticCurveHom_velusqrt(E, K)
sage: phi
Elliptic-curve isogeny (using square-root Vélu) of degree 10009:
From: Elliptic Curve defined by y^2 = x^3 + 5*x + 5 over Finite Field of size 6666679
To: Elliptic Curve defined by y^2 = x^3 + 227975*x + 3596133 over Finite Field of size 6666679
sage: phi.codomain()
Elliptic Curve defined by y^2 = x^3 + 227975*x + 3596133 over Finite Field of size 6666679
Note that the isogeny is usually not identical to the one computed by
EllipticCurveIsogeny
:
sage: psi = EllipticCurveIsogeny(E, K)
sage: psi
Isogeny of degree 10009
from Elliptic Curve defined by y^2 = x^3 + 5*x + 5 over Finite Field of size 6666679
to Elliptic Curve defined by y^2 = x^3 + 5344836*x + 3950273 over Finite Field of size 6666679
However, they are certainly separable isogenies with the same kernel and must therefore be equal up to post-isomorphism:
sage: isos = psi.codomain().isomorphisms(phi.codomain())
sage: sum(iso * psi == phi for iso in isos)
1
Just like
EllipticCurveIsogeny
,
the constructor supports a model
keyword argument:
sage: E = EllipticCurve(GF(6666679), [1,1])
sage: K = E(9091, 517864)
sage: phi = EllipticCurveHom_velusqrt(E, K, model='montgomery')
sage: phi
Elliptic-curve isogeny (using square-root Vélu) of degree 2999:
From: Elliptic Curve defined by y^2 = x^3 + x + 1 over Finite Field of size 6666679
To: Elliptic Curve defined by y^2 = x^3 + 1559358*x^2 + x over Finite Field of size 6666679
Internally, EllipticCurveHom_velusqrt
works on short
Weierstraß curves, but it performs the conversion automatically:
sage: E = EllipticCurve(GF(101), [1,2,3,4,5])
sage: K = E(1, 2)
sage: K.order()
37
sage: EllipticCurveHom_velusqrt(E, K)
Elliptic-curve isogeny (using square-root Vélu) of degree 37:
From: Elliptic Curve defined by y^2 + x*y + 3*y = x^3 + 2*x^2 + 4*x + 5 over Finite Field of size 101
To: Elliptic Curve defined by y^2 = x^3 + 66*x + 86 over Finite Field of size 101
However, this does imply not all elliptic curves are supported. Curves without a short Weierstraß model exist in characteristics \(2\) and \(3\):
sage: F.<t> = GF(3^3)
sage: E = EllipticCurve(F, [1,1,1,1,1])
sage: P = E(t^2+2, 1)
sage: P.order()
19
sage: EllipticCurveHom_velusqrt(E, P)
Traceback (most recent call last):
...
NotImplementedError: only implemented for curves having a short Weierstrass model
Furthermore, the implementation is restricted to finite fields, since this appears to be the most relevant application for the square-root Vélu algorithm:
sage: E = EllipticCurve('26b1')
sage: P = E(1,0)
sage: P.order()
7
sage: EllipticCurveHom_velusqrt(E, P)
Traceback (most recent call last):
...
NotImplementedError: only implemented for elliptic curves over finite fields
Note
Some of the methods inherited from EllipticCurveHom
compute data
whose size is linear in the degree; this includes kernel polynomial and
rational maps. In consequence, those methods cannot possibly run in the
otherwise advertised square-root complexity, as merely storing the result
already takes linear time.
AUTHORS:
Lorenz Panny (2022)
- class sage.schemes.elliptic_curves.hom_velusqrt.EllipticCurveHom_velusqrt(E, P, *, codomain=None, model=None, Q=None)#
Bases:
EllipticCurveHom
This class implements separable odd-degree isogenies of elliptic curves over finite fields using the square-root Vélu algorithm.
The complexity is \(\tilde O(\sqrt{\ell})\) base-field operations, where \(\ell\) is the degree.
REFERENCES: [BDLS2020]
INPUT:
E
– an elliptic curve over a finite fieldP
– a point on \(E\) of odd order \(\geq 9\)codomain
– codomain elliptic curve (optional)model
– string (optional); input tocompute_model()
Q
– a point on \(E\) outside \(\langle P\rangle\), orNone
EXAMPLES:
sage: from sage.schemes.elliptic_curves.hom_velusqrt import EllipticCurveHom_velusqrt sage: F.<t> = GF(10009^3) sage: E = EllipticCurve(F, [t,t]) sage: K = E(2154*t^2 + 5711*t + 2899, 7340*t^2 + 4653*t + 6935) sage: phi = EllipticCurveHom_velusqrt(E, K); phi Elliptic-curve isogeny (using square-root Vélu) of degree 601: From: Elliptic Curve defined by y^2 = x^3 + t*x + t over Finite Field in t of size 10009^3 To: Elliptic Curve defined by y^2 = x^3 + (263*t^2+3173*t+4759)*x + (3898*t^2+6111*t+9443) over Finite Field in t of size 10009^3 sage: phi(K) (0 : 1 : 0) sage: P = E(2, 3163*t^2 + 7293*t + 5999) sage: phi(P) (6085*t^2 + 855*t + 8720 : 8078*t^2 + 9889*t + 6030 : 1) sage: Q = E(6, 5575*t^2 + 6607*t + 9991) sage: phi(Q) (626*t^2 + 9749*t + 1291 : 5931*t^2 + 8549*t + 3111 : 1) sage: phi(P + Q) (983*t^2 + 4894*t + 4072 : 5047*t^2 + 9325*t + 336 : 1) sage: phi(P) + phi(Q) (983*t^2 + 4894*t + 4072 : 5047*t^2 + 9325*t + 336 : 1)
See also
- dual()#
Return the dual of this square-root Vélu isogeny as an
EllipticCurveHom
.Note
The dual is computed by
EllipticCurveIsogeny
, hence it does not benefit from the square-root Vélu speedup.EXAMPLES:
sage: E = EllipticCurve(GF(101^2), [1, 1, 1, 1, 1]) sage: K = E.cardinality() // 11 * E.gens()[0] sage: phi = E.isogeny(K, algorithm='velusqrt'); phi Elliptic-curve isogeny (using square-root Vélu) of degree 11: From: Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 + x + 1 over Finite Field in z2 of size 101^2 To: Elliptic Curve defined by y^2 = x^3 + 39*x + 40 over Finite Field in z2 of size 101^2 sage: phi.dual() Isogeny of degree 11 from Elliptic Curve defined by y^2 = x^3 + 39*x + 40 over Finite Field in z2 of size 101^2 to Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 + x + 1 over Finite Field in z2 of size 101^2 sage: phi.dual() * phi == phi.domain().scalar_multiplication(11) True sage: phi * phi.dual() == phi.codomain().scalar_multiplication(11) True
- inseparable_degree()#
Return the inseparable degree of this square-root Vélu isogeny.
Since
EllipticCurveHom_velusqrt
only implements separable isogenies, this method always returns one.
- kernel_polynomial()#
Return the kernel polynomial of this square-root Vélu isogeny.
Note
The data returned by this method has size linear in the degree.
EXAMPLES:
sage: E = EllipticCurve(GF(65537^2,'a'), [5,5]) sage: K = E.cardinality()//31 * E.gens()[0] sage: phi = E.isogeny(K, algorithm='velusqrt') sage: h = phi.kernel_polynomial(); h x^15 + 21562*x^14 + 8571*x^13 + 20029*x^12 + 1775*x^11 + 60402*x^10 + 17481*x^9 + 46543*x^8 + 46519*x^7 + 18590*x^6 + 36554*x^5 + 36499*x^4 + 48857*x^3 + 3066*x^2 + 23264*x + 53937 sage: h == E.isogeny(K).kernel_polynomial() True sage: h(K.x()) 0
- rational_maps()#
Return the pair of explicit rational maps of this square-root Vélu isogeny as fractions of bivariate polynomials in \(x\) and \(y\).
Note
The data returned by this method has size linear in the degree.
EXAMPLES:
sage: E = EllipticCurve(GF(101^2), [1, 1, 1, 1, 1]) sage: K = (E.cardinality() // 11) * E.gens()[0] sage: phi = E.isogeny(K, algorithm='velusqrt'); phi Elliptic-curve isogeny (using square-root Vélu) of degree 11: From: Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 + x + 1 over Finite Field in z2 of size 101^2 To: Elliptic Curve defined by y^2 = x^3 + 39*x + 40 over Finite Field in z2 of size 101^2 sage: phi.rational_maps() ((-17*x^11 - 34*x^10 - 36*x^9 + ... - 29*x^2 - 25*x - 25)/(x^10 + 10*x^9 + 19*x^8 - ... + x^2 + 47*x + 24), (-3*x^16 - 6*x^15*y - 48*x^15 + ... - 49*x - 9*y + 46)/(x^15 + 15*x^14 - 35*x^13 - ... + 3*x^2 - 45*x + 47))
- scaling_factor()#
Return the Weierstrass scaling factor associated to this square-root Vélu isogeny.
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 isogeny and \(\omega_i\) are the standard Weierstrass differentials on \(E_i\) defined by \(\mathrm dx/(2y+a_1x+a_3)\).
EXAMPLES:
sage: E = EllipticCurve(GF(101^2), [1, 1, 1, 1, 1]) sage: K = (E.cardinality() // 11) * E.gens()[0] sage: phi = E.isogeny(K, algorithm='velusqrt', model='montgomery'); phi Elliptic-curve isogeny (using square-root Vélu) of degree 11: From: Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 + x + 1 over Finite Field in z2 of size 101^2 To: Elliptic Curve defined by y^2 = x^3 + 61*x^2 + x over Finite Field in z2 of size 101^2 sage: phi.scaling_factor() 55 sage: phi.scaling_factor() == phi.formal()[1] True
- x_rational_map()#
Return the \(x\)-coordinate rational map of this square-root Vélu isogeny as a univariate rational function in \(x\).
Note
The data returned by this method has size linear in the degree.
EXAMPLES:
sage: E = EllipticCurve(GF(101^2), [1, 1, 1, 1, 1]) sage: K = (E.cardinality() // 11) * E.gens()[0] sage: phi = E.isogeny(K, algorithm='velusqrt'); phi Elliptic-curve isogeny (using square-root Vélu) of degree 11: From: Elliptic Curve defined by y^2 + x*y + y = x^3 + x^2 + x + 1 over Finite Field in z2 of size 101^2 To: Elliptic Curve defined by y^2 = x^3 + 39*x + 40 over Finite Field in z2 of size 101^2 sage: phi.x_rational_map() (84*x^11 + 67*x^10 + 65*x^9 + ... + 72*x^2 + 76*x + 76)/(x^10 + 10*x^9 + 19*x^8 + ... + x^2 + 47*x + 24) sage: phi.x_rational_map() == phi.rational_maps()[0] True
- class sage.schemes.elliptic_curves.hom_velusqrt.FastEllipticPolynomial(E, n, P, Q=None)#
Bases:
object
A class to represent and evaluate an elliptic polynomial, and optionally its derivative, in essentially square-root time.
The elliptic polynomials computed by this class are of the form
\[h_S(Z) = \prod_{i\in S} (Z - x(Q + [i]P))\]where \(P\) is a point of odd order \(n \geq 5\) and \(Q\) is either
None
, in which case it is assumed to be \(\infty\), or an arbitrary point which is not a multiple of \(P\).The index set \(S\) is chosen as follows:
If \(Q\) is given, then \(S = \{0,1,2,3,...,n-1\}\).
If \(Q\) is omitted, then \(S = \{1,3,5,...,n-2\}\). Note that in this case, \(h_{\{1,2,3,...,n-1\}}\) can be computed as \(h_S^2\) since \(n\) is odd.
INPUT:
E
– an elliptic curve in short Weierstraß formn
– an odd integer \(\geq 5\)P
– a point on \(E\)Q
– a point on \(E\), orNone
ALGORITHM: [BDLS2020], Algorithm 2
Note
Currently only implemented for short Weierstraß curves.
EXAMPLES:
sage: from sage.schemes.elliptic_curves.hom_velusqrt import FastEllipticPolynomial sage: E = EllipticCurve(GF(71), [5,5]) sage: P = E(4, 35) sage: hP = FastEllipticPolynomial(E, P.order(), P); hP Fast elliptic polynomial prod(Z - x(i*P) for i in range(1,n,2)) with n = 19, P = (4 : 35 : 1) sage: hP(7) 19 sage: prod(7 - (i*P).x() for i in range(1,P.order(),2)) 19
Passing \(Q\) changes the index set:
sage: Q = E(0, 17) sage: hPQ = FastEllipticPolynomial(E, P.order(), P, Q) sage: hPQ(7) 58 sage: prod(7 - (Q+i*P).x() for i in range(P.order())) 58
The call syntax has an optional keyword argument
derivative
, which will make the function return the pair \((h_S(\alpha), h_S'(\alpha))\) instead of just \(h_S(\alpha)\):sage: hP(7, derivative=True) (19, 15) sage: R.<Z> = E.base_field()[] sage: HP = prod(Z - (i*P).x() for i in range(1,P.order(),2)) sage: HP Z^9 + 16*Z^8 + 57*Z^7 + 6*Z^6 + 45*Z^5 + 31*Z^4 + 46*Z^3 + 10*Z^2 + 28*Z + 41 sage: HP(7) 19 sage: HP.derivative()(7) 15
sage: hPQ(7, derivative=True) (58, 62) sage: R.<Z> = E.base_field()[] sage: HPQ = prod(Z - (Q+i*P).x() for i in range(P.order())) sage: HPQ Z^19 + 53*Z^18 + 67*Z^17 + 39*Z^16 + 56*Z^15 + 32*Z^14 + 44*Z^13 + 6*Z^12 + 27*Z^11 + 29*Z^10 + 38*Z^9 + 48*Z^8 + 38*Z^7 + 43*Z^6 + 21*Z^5 + 25*Z^4 + 33*Z^3 + 49*Z^2 + 60*Z sage: HPQ(7) 58 sage: HPQ.derivative()(7) 62
The input can be an element of any algebra over the base ring:
sage: R.<T> = GF(71)[] sage: S.<t> = R.quotient(T^2) sage: hP(7 + t) 15*t + 19