Î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)#
Bases:
sage.schemes.elliptic_curves.hom.EllipticCurveHomThis 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 fieldP– a point on \(E\) of odd order \(\geq 5\)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 Î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
- class sage.schemes.elliptic_curves.hom_velusqrt.FastEllipticPolynomial(E, n, P, Q=None)#
Bases:
objectA 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).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:
objectA 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)