# √élu Algorithm for Elliptic-Curve Isogenies#

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 √é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 √é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 √é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 √é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

Currently EllipticCurveHom_velusqrt does not implement all methods of EllipticCurveHom. This will hopefully change in the future.

AUTHORS:

• Lorenz Panny (2022)

class sage.schemes.elliptic_curves.hom_velusqrt.EllipticCurveHom_velusqrt(E, P, codomain, model, Q)#

This class implements separable odd-degree isogenies of elliptic curves over finite fields using the √é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 field

• P – a point on $$E$$ of odd order $$\geq 5$$

• codomain – codomain elliptic curve (optional)

• model – string (optional); input to compute_model()

• Q – a point on $$E$$ outside $$\langle P\rangle$$, or None

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 √é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)

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ß form

• n – an odd integer $$\geq 5$$

• P – a point on $$E$$

• Q – a point on $$E$$, or None

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).xy()[0] 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).xy()[0] 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).xy()[0] 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).xy()[0] 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

class sage.schemes.elliptic_curves.hom_velusqrt.ProductTree(leaves)#

Bases: object

A simple product tree.

INPUT:

• leaves – a sequence of elements in a common ring

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_velusqrt import ProductTree
sage: R.<x> = GF(101)[]
sage: vs = [x - i for i in range(1,10)]
sage: tree = ProductTree(vs)
sage: tree.value()
x^9 + 56*x^8 + 62*x^7 + 44*x^6 + 47*x^5 + 42*x^4 + 15*x^3 + 11*x^2 + 12*x + 13
sage: tree.remainders(x^7 + x + 1)
[3, 30, 70, 27, 58, 72, 98, 98, 23]
sage: tree.remainders(x^100)
[1, 1, 1, 1, 1, 1, 1, 1, 1]

sage: vs = prime_range(100)
sage: tree = ProductTree(vs)
sage: tree.value().factor()
2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97
sage: tree.remainders(3599)
[1, 2, 4, 1, 2, 11, 12, 8, 11, 3, 3, 10, 32, 30, 27, 48, 0, 0, 48, 49, 22, 44, 30, 39, 10]


We can access the individual layers of the tree:

sage: tree.layers
[(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97),
(6, 35, 143, 323, 667, 1147, 1763, 2491, 3599, 4757, 5767, 7387, 97),
(210, 46189, 765049, 4391633, 17120443, 42600829, 97),
(9699690, 3359814435017, 729345064647247, 97),
(32589158477190044730, 70746471270782959),
(2305567963945518424753102147331756070,)]


Note

Use this class if you need the remainders() method. To compute just the product, prod() is likely faster.

remainders(x)#

Given a value $$x$$, return a list of all remainders of $$x$$ modulo the leaves of this product tree.

The base ring must support the % operator for this method to work.

INPUT:

• x – an element of the base ring of this product tree

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_velusqrt import ProductTree
sage: vs = prime_range(100)
sage: tree = ProductTree(vs)
sage: n = 1085749272377676749812331719267
sage: tree.remainders(n)
[1, 1, 2, 1, 9, 1, 7, 15, 8, 20, 15, 6, 27, 11, 2, 6, 0, 25, 49, 5, 51, 4, 19, 74, 13]
sage: [n % v for v in vs]
[1, 1, 2, 1, 9, 1, 7, 15, 8, 20, 15, 6, 27, 11, 2, 6, 0, 25, 49, 5, 51, 4, 19, 74, 13]

value()#

Return the value represented by this product tree (i.e., the product of all leaves).

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_velusqrt import ProductTree
sage: R.<x> = GF(101)[]
sage: vs = [x - i for i in range(1,10)]
sage: tree = ProductTree(vs)
sage: tree.value()
x^9 + 56*x^8 + 62*x^7 + 44*x^6 + 47*x^5 + 42*x^4 + 15*x^3 + 11*x^2 + 12*x + 13
sage: tree.value() == prod(vs)
True

sage.schemes.elliptic_curves.hom_velusqrt.prod_with_derivative(pairs)#

Given a list of pairs $$(f, \partial f)$$ of ring elements, return the pair $$(\prod f, \partial \prod f)$$, assuming $$\partial$$ is an operator obeying the standard product rule.

This function is entirely algebraic, hence still works when the elements $$f$$ and $$\partial f$$ are all passed through some ring homomorphism first. (See the polynomial-evaluation example below.)

INPUT:

• pairs – a sequence of tuples $$(f, \partial f)$$ of elements of a common ring

ALGORITHM:

This function wraps the given pairs in a thin helper class that automatically applies the product rule whenever multiplication is invoked, then calls prod() on the wrapped pairs.

EXAMPLES:

sage: from sage.schemes.elliptic_curves.hom_velusqrt import prod_with_derivative
sage: R.<x> = ZZ[]
sage: fs = [x^2 + 2*x + 3, 4*x + 5, 6*x^7 + 8*x + 9]
sage: prod(fs)
24*x^10 + 78*x^9 + 132*x^8 + 90*x^7 + 32*x^4 + 140*x^3 + 293*x^2 + 318*x + 135
sage: prod(fs).derivative()
240*x^9 + 702*x^8 + 1056*x^7 + 630*x^6 + 128*x^3 + 420*x^2 + 586*x + 318
sage: F, dF = prod_with_derivative((f, f.derivative()) for f in fs)
sage: F
24*x^10 + 78*x^9 + 132*x^8 + 90*x^7 + 32*x^4 + 140*x^3 + 293*x^2 + 318*x + 135
sage: dF
240*x^9 + 702*x^8 + 1056*x^7 + 630*x^6 + 128*x^3 + 420*x^2 + 586*x + 318


The main reason for this function to exist is that it allows us to evaluate the derivative of a product of polynomials at a point $$\alpha$$ without ever fully expanding the product as a polynomial:

sage: alpha = 42
sage: F(alpha)
442943981574522759
sage: dF(alpha)
104645261461514994
sage: us = [f(alpha) for f in fs]
sage: vs = [f.derivative()(alpha) for f in fs]
sage: prod_with_derivative(zip(us, vs))
(442943981574522759, 104645261461514994)