ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
arXiv:2607.05160v1 [cs.SC] 6 Jul 2026
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA Abstract. We present a new algebraic modeling of the Supersingular Isogeny Problem as a system of multivariate polynomial equations, in the case where the elliptic curves are connected by an isogeny whose degree is a power of 2 or 3. This modeling relies on Renes formulas for elliptic curves in Montgomery form (degree 2) or triangular form (degree 3). We investigate several algebraic properties of these systems: we prove that they are zero-dimensional, compute the dimension of their highest degree part, and show that they are not in generic coordinates. Experimental results show that solving these systems via Gröbner basis techniques is significantly faster than solving the algebraic modeling with modular polynomials.
Introduction We fix a prime number p > 3 and let E and E ′ be two supersingular elliptic curves defined over Fp2 such that there exists a degree d isogeny φ : E → E ′ . The Supersingular Isogeny Problem (SIP) asks to find φ. When d and p are sufficiently large, a random instance of this problem is believed to be computationally difficult to solve, even using a quantum computer. For this reason, it has been used as the underlying problem for several post-quantum cryptographic schemes, such as the signature scheme SQIsign [20], which, at the time of writing, is admitted to Round 3 of the NIST call for post-quantum signature schemes. For this reason, the SIP has been widely studied and several algorithms and methods have been proposed in the literature. We note that, since the degree of isogenies is multiplicative under composition, the main difficulty in solving the SIP arises when the degree d is a power of a prime ℓ ̸= p. In this setting, the most efficient approaches exploit structural properties of the graph of ℓ-isogenies between supersingular elliptic curves [15, 17, 21, 26]. Given the growing importance of post-quantum cryptography, both the cryptanalysis of proposed schemes and the study of the hardness of their underlying problems have received increasing attention in recent years. A comprehensive security assessment requires considering attacks originating from different areas of post-quantum cryptography. In this context, algebraic modeling and algebraic attacks have emerged as important tools. In the literature, several algebraic models have been proposed and studied for problems arising in code-based cryptography [11, 19, 32, 38] and lattice-based cryptography [2, 3, 42]. In contrast, algebraic modeling of problems in isogeny-based cryptography has received comparatively less attention [44]. A natural approach to modeling the Supersingular Isogeny Problem as a system of multivariate polynomial equations is via modular polynomials [48, §10]. Given a positive integer N ̸= p the N -th modular polynomial ΦN (X, Y ) is a polynomial (with integer coefficients) with the property that ΦN (j1 , j2 ) = 0 if and only if j1 , j2 are the j-invariants of elliptic curves that are related by an isogeny of degree N . So, if N = ℓe , where ℓ is a prime number, given the j-invariants jstart , jfinish of two elliptic curves Estart , Efinish connected by a N -isogeny φ, we can reduce the SIP to several smaller instances of the SIP in degree ℓ by solving a multivariate polynomial system (see Polynomial system 1) with modular polynomials, whose solutions represent all possible paths from Key words and phrases. Supersingular Isogeny Problem, Gröbner bases, solving degree, algebraic modeling. 1
2
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
Estart to Efinish in the ℓ-isogeny graph. This approach has been studied in the paper [44]. There, the authors propose the algebraic model and study the complexity of solving the corresponding polynomial system via Gröbner basis techniques. In this paper, we propose two distinct algebraic models for the SIP: one for isogenies whose degree is a power of 2, and one for isogenies whose degree is a power of 3. These two cases are the most relevant for cryptographic applications. The main ideas, which originate from the works of Renes [35], Burdges–De Feo [10], and Costello–Hisil [16], are as follows. If an elliptic curve E is given in Montgomery form, then the 2-isogenies with domain E can be described explicitly in terms of the x-coordinates of the 2-torsion points of E. More precisely, if α ∈ Fp2 is the x-coordinate of a 2-torsion point of E, then one can construct a 2-isogeny φα : E → E(α), where E(α) can also be expressed in Montgomery form, allowing us to iteratively describe also the 2-isogenies with domain E(α). Moreover, the 2-isogeny with kernel ⟨(0, 0)⟩ is the dual isogeny of φα . By proceeding in this way, we can explicitly construct a non-backtracking path (a sequence in which no two consecutive isogenies are dual to each other) of 2-isogenies starting from E. We use these formulas to derive multivariate polynomials, which we call Renes polynomials (Definition 3.7), playing a role analogous to that of modular polynomials for curves in Montgomery form. Using these polynomials, we construct a system of polynomial equations modeling the SIP for curves in Montgomery form and isogenies of degree a power of 2 (Polynomial System 2). One key difference with respect to the modular polynomials setting is that, once a j-invariant is fixed, there exist several non-isomorphic elliptic curves in Montgomery with that j-invariant. As a consequence, the resulting polynomial system contains a polynomial of degree 12, which significantly impacts the efficiency of solving the system. However, this issue can be mitigated by decomposing the problem into six quadratic systems (Polynomial System 3), whose computations can be parallelized. The case of degree 3 is analogous, with the key difference that, in order to explicitly describe the 3-isogenies with domain an elliptic curve E, the curve must be expressed in triangular form. As in the degree 2 setting, the central idea is to ensure that the point (0, 0) is a 3-torsion point. In this framework, the 3-isogenies with kernel ⟨(0, 0)⟩ correspond to the dual isogenies along the path, and we can exclude them to obtain a non-backtracking path. As before, there exist multiple non-isomorphic curves in triangular form sharing the same j-invariant. Consequently, we construct 12 quadratic systems (Polynomial System 5), whose computations can be parallelized. Once the algebraic models have been constructed, we analyze the complexity of solving them using Gröbner basis techniques and compare it with that of systems based on modular polynomials. A key parameter for estimating the complexity of solving a multivariate polynomial system F via linear-algebra-based Gröbner basis algorithms is the solving degree, denoted sd(F). Informally, the solving degree is the highest degree reached by the polynomials appearing during the computation of a Gröbner basis using such algorithms. Estimating this degree without explicitly solving the system, and thus understanding how it grows with respect to the input parameters (such as the number of variables, the number of equations, and their degrees), is notoriously difficult. Several invariants have been introduced to address this problem, including the degree of regularity [4, 39] and the Castelnuovo-Mumford regularity [12]. The degree of regularity is defined when the highestdegree homogeneous component F top of the system is zero-dimensional. However, for the systems arising from the algebraic modeling of the SIP, both with modular and Renes polynomials, we show that this condition does not hold (Proposition 5.4). On the other hand, when a system is in generic coordinates, the solving degree is bounded above by the Castelnuovo-Mumford regularity [12], a fundamental invariant in commutative algebra and algebraic geometry. Nevertheless, we prove that the systems under consideration are not in generic coordinates (Proposition 5.7).
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
3
Finally, we perform computational experiments to compare both the running times and the solving degrees of the polynomial systems arising from modular and Renes polynomials (see Section 6). The results show that the approach based on Renes polynomials is significantly faster and typically yields a strictly smaller solving degree. For instance, for a 24-bit prime p, we are able to solve the SIP for isogenies of degree up to 215 with a solving degree of 6. In contrast, for the same parameters using modular polynomials, computations become infeasible beyond degree 212 , with a solving degree of 9. Structure of the paper. In Section 1, we recall some definitions, notations, and results on elliptic curves and polynomial system solving via Gröbner bases. In Section 2, we recall the algebraic modeling with modular polynomials from [44]. In Section 3 and Section 4 we present our algebraic modelings with Renes polynomials in degrees 2 and 3 respectively. In Section 5, we prove some algebraic properties of these systems and in Section 6 we perform some experiments to compare them. Acknowledgments. We thank Luca De Feo for bringing Renes’ work [35] to our attention. We also thank Giulio Codogni, Ignacio M. Jiménez, Guido Lido, and Marzio Mula for several helpful comments on an earlier version of this paper. A. Caminata and A. Sanguineti are supported by the PRIN PNRR 2022 grant P2022J4HRR “Mathematical Primitives for Post Quantum Digital Signatures” and by the MUR Excellence Department Project awarded to Dipartimento di Matematica, Università di Genova, CUP D33C23001110001. A. Caminata is supported by the PRIN 2022 grant 2022K48YYP “Unirationality, Hilbert schemes, and singularities”. S. Sconza’s research is supported by armasuisse Science and Technology. 1. Preliminaries Throughout the paper p denotes a prime number greater than 3. 1.1. Isogeny Problem. An elliptic curve E over a finite field Fq of characteristic p is a projective plane curve which is defined (in affine coordinates) by a Weierstrass equation y 2 = x3 + ax + b with 3 . a, b ∈ Fq and discriminant ∆(E) = 4a3 +27b2 ̸= 0. Its j-invariant is defined as j(E) = 1728 4a34a +27b2 Two elliptic curves have the same j-invariant if and only if they are isomorphic (as algebraic curves) over the algebraic closure Fq of Fq . The set of points of E is endowed with an addition law that makes it into an abelian group whose identity element is OE = [0 : 1 : 0], the unique point at infinity of the curve. The set E(Fq ) of Fq -rational points of E forms a subgroup. An isogeny φ between two elliptic curves E and E ′ is a morphism φ : E → E ′ , which is also a group homomorphism of the underlying group structures. For example, the multiplication-by-m map [m] : E → E is an isogeny. Its kernel, denoted by E[m], is the set of m-torsion points of E. The degree of an isogeny is its degree as morphism. We will write ℓ-isogeny to indicate an isogeny of degree ℓ. The degree is multiplicative under composition of isogenies: if φ and ψ are isogenies such that φ ◦ ψ is defined, then deg(φ ◦ ψ) = deg(φ) · deg(ψ). We say that an isogeny is cyclic if its kernel is a cyclic group. We recall that an isogeny is uniquely determined by its kernel, up to isomorphism. For example, when the degree of the isogeny is not divisible by the characteristic of the field, we have deg(φ) = | ker(φ)|. In particular, if an isogeny has prime degree, then it is necessarily cyclic. Finally, we recall that given an isogeny φ : E → E ′ of degree ℓ, there exists an isogeny φ b : E ′ → E of degree ℓ such that φ ◦ φ b = [ℓ] and φ b ◦ φ = [ℓ]. Such an isogeny φ b is called the dual isogeny of φ.
4
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
Elliptic curves can be partitioned into two disjoint families: ordinary and supersingular elliptic curves. These can be defined in many equivalent ways. For example, we say that an elliptic curve E is supersingular if the subgroup of p-torsion points (where p is the characteristic of the base field Fq ) is trivial, i.e., E[p] = {OE }. Otherwise, E is said to be ordinary and in this case E[p] ∼ = Z/pZ. A distinctive property of supersingular elliptic curves is that their j-invariants are always defined over Fp2 . Whether an elliptic curve is ordinary or supersingular is an isogeny invariant. Namely, if φ : E → E ′ is an isogeny, then E is supersingular (resp. ordinary) if and only if E ′ is supersingular (resp. ordinary). We are interested in the following problem. Problem 1.1 (SIP: Supersingular Isogeny Problem). Given E and E ′ two supersingular elliptic curves defined over Fq , find (if it exists) an isogeny φ : E → E ′ of degree ℓ. A key observation in the study of this problem is that any isogeny of degree ℓ can be decomposed into a sequence of isogenies of prime degree, by factoring ℓ into its prime components. Thus, it is often enough to focus on the Supersingular Isogeny Problem when ℓ is a prime power. In practice, chains of isogenies of prime degree 2 or 3 are often considered. Notice that in this setup all the elliptic curves in the intermediate steps of the chain are supersingular. 1.2. Polynomial system solving via Gröbner bases. In this section, we give a brief overview on how to solve polynomial systems by using Gröbner bases and the related relevant invariants. For consistency with rest of the paper, we fix a finite field Fq (although everything in this section can be defined over any field), and we work over the polynomial ring Fq [x1 , . . . , xn ]. Let T be the set of terms (i.e., monic monomials) of Fq [x1 , . . . , xn ]. A term order < on T is a total order which is compatible with the multiplicative structure, that is m1 < m2 implies m1 m < m2 m, and m1 | m2 implies m1 ≤ m2 . Given a polynomial f we denote by LT< (f ) its leading term, i.e., the largest term of f with respect to the chosen term order. Similarly, given an ideal I, we denote by LT< (I) = (LT< (f ) : f ∈ I), the initial ideal of I, which is generated by all leading terms of polynomials of I. If I is generated by polynomials f1 , . . . , fm , then it holds (LT< (f1 ), . . . , LT< (fm )) ⊆ LT< (I), but the inclusion might be strict in general. When equality holds, we say that f1 , . . . , fm is a Gröbner basis of I (with respect to the given term order). Gröbner bases have a tight connection with polynomial system solving. Namely, the solutions of a zero-dimensional polynomial system fi (x1 , . . . , xn ) = 0 (i = 1, . . . , m) can be read off from a lexicographic Gröbner basis of the corresponding ideal (f1 , . . . , fm ) in Fq [x1 , . . . , xn ] thanks to the Shape Lemma and its extensions (see e.g. [12]). There are several methods to compute Gröbner bases in practice. The oldest one is Buchberger’s algorithm [9]. Some of the fastest methods in use today are the linear-algebra algorithms, such as F4 [23], F5 [24], and XL [18]. The core idea of these algorithms is to compute the Gröbner basis by doing Gaussian reduction on certain matrices, called Macaulay matrices. Let d ∈ Z≥1 , and let T≤d be the set of terms in Fq [x1 , . . . , xn ] of degree less than or equal to d. The Macaulay matrix M≤d of F = {f1 , . . . , fm } is a matrix whose rows are indexed by the polynomials tk,h fk , where k = 1, . . . , m and tk,h ranges through all terms in T≤d such that deg(tk,h fk ) ≤ d, and columns are indexed by the terms in T≤d . The (i, j) entry of M≤d is the coefficient of the j-th term in the polynomial of the i-th row. When d is large enough, performing Gaussian elimination on M≤d provides a Gröbner basis of (F). The smallest d such that this happens is called solving degree of F and we denote it by sd≤ (F). We often omit the subscript ≤ when the term order is clear from the context. In practice, the linear-algebra-based methods mentioned above make extensive use of this idea, carefully selecting suitable submatrices of the Macaulay matrices in order to minimize the number of
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
5
zero entries and avoid unnecessary computations. Moreover, although a Gröbner basis with respect to the lexicographic order is ultimately required to extract the solutions of the system, it is often more efficient to first compute a Gröbner basis with respect to the degree-reverse lexicographic order, and then convert it to lexicographic form using the FGLM algorithm [25] or related techniques. That being said, the main computational bottleneck in solving such systems is typically the Gaussian elimination performed on the largest Macaulay matrix encountered during the computation. The size of this matrix depends on the number of variables n, the number of polynomials m, and the solving degree sd≤ (F). For this reason, it is crucial to determine, or at least accurately estimate, the solving degree of a polynomial system and understand how it scales with respect to the system’s parameters. However, computing the solving degree a priori is generally very difficult. To address this issue, several alternative invariants, often more tractable, have been introduced and related to the solving degree, including the degree of regularity [4], the last fall degree [13, 28], the first fall degree [22], and the Castelnuovo-Mumford regularity [12]. 2. Algebraic Modeling with Modular Polynomials The first natural way to produce an algebraic modeling for the Supersingular Isogeny Problem is using modular polynomials. This was explored by Takahashi et al. [44]. We briefly recall this modeling, which will serve us as a comparison. 2.1. Background on modular polynomials. We fix a finite field Fq of characteristic p and let N > 1 be an integer coprime with p. Then, there exists a polynomial ΦN ∈ Z[X, Y ], called N -th modular polynomial, such that for all j1 , j2 ∈ Fq it holds that ΦN (j1 , j2 ) = 0 if and only if j1 , j2 are the j-invariants of elliptic curves over Fq that are related by an isogeny of degree N defined over Fp (see e.g. [29, §11.9]). In the following proposition we collect some useful properties of modular polynomials. Proposition 2.1. Let N > 1 be an integer. The modular polynomial ΦN (X, Y ) ∈ Z[X, Y ] satisfies the following properties: (1) ΦN (X, Y ) = ΦN (Y, X); (2) ΦN is monic and it has degree N + 1 both in X and Y ; N N (3) If N is prime, then the highest degree form Φtop N of ΦN is −X Y . Proof. The first two properties are well known (see e.g. [43, Lectures 19 and 20]). We address the third. Let N be prime, by combining [43, Theorem 19.14 and Lemma 20.9] we get that ΦN (X, Y ) is monic in X and in Y and the top degree part of ΦN (X, X) is −X 2N . Therefore, we can write ΦN (X, Y ) = X N +1 + Y N +1 − X N Y N + {monomials of degree < 2N }. This tells us exactly that ΦN (X, Y )top = −X N Y N .
□
Example 2.2. The first two modular polynomials are the following. Φ2 (X, Y ) = X 3 + Y 3 − X 2 Y 2 + 1488(X 2 Y + XY 2 ) − 162000(X 2 + Y 2 )+ + 40773375XY + 8748000000(X + Y ) − 157464000000000; Φ3 (X, Y ) = (X + Y )4 − X 3 Y 3 + 2232X 2 Y 2 (X + Y ) + 36864000(X + Y )3 + − 1069960XY (X + Y )2 + 2590058000X 2 Y 2 + + 8900112384000XY (X + Y ) + 452984832000000(X + Y )2 + − 771751936000000000XY + 1855425871872000000000(X + Y ).
(1)
6
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
Higher degree modular polynomials are larger. However, recall that they can be constructed algorithmically, for example by using the procedure outlined in [14]. One subtlety is that the vanishing of ΦN (j1 , j2 ) is equivalent to the existence of an isogeny which is defined over the algebraic closure Fq , while we are interested in working over a finite field. In our setup, this is not a problem. We address it in the following remark. Remark 2.3. First of all, we recall that every supersingular elliptic curve has j-invariant defined over Fp2 and it is isomorphic (over Fp ) to an elliptic curve defined over Fp2 ([41, Remark 9.7]). Now, if E1 and E2 are two supersingular elliptic curves defined over Fp2 that are connected via an isogeny of degree N over Fp , then there exist two elliptic curves E1′ , E2′ , defined over Fp2 , such that E1 ∼ = E2′ over Fp and there exists a N -isogeny between E1′ and E2′ defined over Fp2 = E1′ and E2 ∼ (see [30, Lemma 5.2]). Therefore, when considering chain of isogenies up to taking those isomorphic curves at the beginning and at the end, we may restrict without loss of generality to work only with supersingular curves and isogenies defined over Fp2 . 2.2. The modeling. Let ℓ ̸= p be a prime number. Given two supersingular elliptic curves Estart , Efinish over Fp2 with j-invariants jstart and jfinish that are connected via an isogeny φ of degree ℓm (m ∈ Z≥1 ), we want to find the j-invariants of the curves in the path that connects them, i.e, the j-invariants of curves E1 , . . . , Em−1 such that φ1
φ2
φm
Estart −→ E1 −→ E2 → · · · → Em−1 −−→ Efinish , where the φi ’s are isogenies of degree ℓ such that
(2)
φm ◦ φm−1 ◦ · · · ◦ φ1 = φ. Now, we can set up the following polynomial system. Polynomial system 1: Modular Polynomials Sm−1 = Fp2 [j1 , . . . , jm−1 ] Mℓ,m = [Φℓ (jstart , j1 ), Φℓ (j1 , j2 ), . . . , Φℓ (jm−2 , jm−1 ), Φℓ (jm−1 , jfinish )] ⊆ Sm−1 Φℓ (jstart , j1 ) = 0 Φℓ (j1 , j2 ) = 0 ······ Φℓ (jm−2 , jm−1 ) = 0 Φℓ (jm−1 , jfinish ) = 0 The properties of modular polynomials immediately give us the following result. Theorem 2.4. Let Estart , Efinish be two supersingular elliptic curves defined over Fp2 which are connected by an ℓm -isogeny φ, with ℓ a prime number and m ∈ Z>1 . Let (j1 , . . . , jm−1 ) ∈ Fm−1 be p2 a solution of Polynomial system 1, then j1 , . . . , jm−1 are the j-invariants of supersingular elliptic curves in a chain of isogenies of degree ℓ that connects Estart and Efinish as in (2). Theorem 2.4 tells us that finding a solution of Polynomial system 1 allows us to reduce an instance of the Supersingular Isogeny Problem (SIP) of degree ℓm between Estart and Efinish to m instances of the SIP of degree ℓ. When ℓ is small (such as ℓ = 2, 3) the isogenies φi ’s are easy to find. In fact, we point out that up to ℓ ≤ 31, there exist SageMath libraries [46, 47] that allow the efficient writing of all the ℓ-isogenies of the decomposition.
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
7
We postpone to Section 5 and Section 6 an analysis of the algebraic properties of Polynomial system 1 and a report on some experiments that we performed for ℓ = 2, 3. 3. Algebraic Modeling with Renes Polynomials in degree 2 In this section, we consider chain of isogenies of degree 2. Given a supersingular elliptic curve E we have three isogenies of degree 2 with domain the curve E, indeed the 2-isogeny graph is 3-regular [31]. The kernel of a 2-isogeny is a subgroup of order 2. In other words, we have a degree 2 isogeny associated to each non trivial element of E[2]. It turns out that when E is in Montgomery form, these elements and the corresponding isogenies can be explicitly written thanks to Renes formulas [10, 16, 35]. We use these formulas to construct polynomials and build an algebraic modeling for SIP. 3.1. Montgomery curves and Renes formulas. A supersingular elliptic curve E over Fp2 is written in Montgomery form if E : By 2 = x3 + Ax2 + x, with A, B ∈ Fp2 . It is clear that a nonsingular curve in Montgomery form is elliptic, while not every elliptic curve in Weierstrass form can be transformed into a Montgomery form. A necessary and sufficient condition is given in the following theorem from [33]. Theorem 3.1 ([33]). Let E : y 2 = x3 + ax + b be an elliptic curve defined over Fq . Then E is isomorphic to a Montgomery curve E ′ : By 2 = x3 + Ax2 + x over Fq if and only if (1) E has an Fq -rational 2-torsion point (α, 0); (2) 3α2 + a = s2 for some s ∈ Fq ∖ {0}. In this case, the coefficients of E ′ are A = 3αs−1 and B = s−1 . Remark 3.2. If E : By 2 = x3 + Ax2 + x is an elliptic curve in Montgomery form over Fp2 , then it is isomorphic (over Fp4 ) to the curve E ′ : y 2 = x3 + Ax2 + x, which is a quadratic twist of E. Thus, for simplicity in what follows we will restrict to curves in Montgomery form with B = 1 and A ∈ Fp2 . We consider a supersingular elliptic curve E written in Montgomery form as E : y 2 = x3 + Ax2 + x.
(3)
The 2-torsion points of E are E[2] = {OE , (0, 0), (α, 0), (α−1 , 0)}, where α ∈ Fp4 is a root of x2 + Ax + 1, and A = −α − α−1 . For curves with j-invariant ̸= 0, 1728 the roots α, α−1 of x2 + Ax + 1 are indeed in Fp2 . Lemma 3.3. Let E be a supersingular elliptic curve defined over Fp2 such that |E(Fp2 )| = (p ± 1)2 . Then E[2] ⊆ E(Fp2 ), i.e., the 2-torsion points of E are Fp2 -rational. Proof. Thanks to [40, Lemma 4.8 (ii)], we have that E(Fp2 ) ∼ = Z/(p + 1)Z × Z/(p + 1)Z or E(Fp2 ) ∼ = Z/(p − 1)Z × Z/(p − 1)Z. On the other hand, we have that E[2] ∼ = Z/2Z × Z/2Z. Since 2 | p ± 1, it holds that Z/(p ± 1)Z has a subgroup of order 2, and it must be Z/2Z. So we must have that E[2] ⊆ E(Fp2 ). □
8
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
Remark 3.4. The condition |E(Fp2 )| = (p ± 1)2 in Lemma 3.3 may seem restrictive, however it is satisfied by any supersingular elliptic curve E with j(E) ̸= 0, 1728. Indeed, let t = p2 + 1 − |E(Fp2 )| be the trace of the Frobenius endomorphism ϕp2 on E. Since E is supersingular, by Hasse’s bound we have that t ∈ {0, ±p, ±2p}. If t = 0, then the characteristic polynomial of the Frobenius ϕp2 is h(x) = x2 + p2 . Since h(x) has a root ϕp2 in End(E), its discriminant ∆ = −4p2 must be a square. This implies that E has a nontrivial automorphism of order 4. Since the characteristic of the field is ̸= 2, 3, this happens only if j(E) = 1728 [41, Theorem 10.1]. With a similar argument one can show that t = ±p forces j(E) = 0. Thus, if j(E) ̸= 0, 1728, we have t = ±2p and |E(Fp2 )| = (p ± 1)2 (see also [1]). Now, we consider a supersingular elliptic curve E over Fp2 written in Montgomery form as in (3) with |E(Fp2 )| = (p ± 1)2 . By Lemma 3.3, the 2-torsion points of E are in Fp2 . Thus, we can factor the polynomial x2 + Ax + 1 over Fp2 and write E in simplified Montgomery form [10]: E : y 2 = x(x − α)(x − α−1 ), with α ∈ Fp2 . The subgroups of order 2 ⟨(α, 0)⟩ and ⟨(α−1 , 0)⟩ are the kernels of two distinct 2-isogenies φ1 and φ2 with domain E. It turns out that the codomain elliptic curves of φ1 and φ2 can also be written in simplified Montgomery form. The following lemma due to Renes [35, Proposition 2] formalizes our claims. Lemma 3.5 (Renes formulas, degree 2). Let E be a supersingular elliptic curve over Fp2 written in simplified Montgomery form y 2 = x(x − α)(x − α−1 ). Then, there exist two 2-isogenies φ1 : E → E1 , φ2 : E → E2 defined over Fp2 such that E1 , E2 are defined over Fp2 and can be written in Montgomery form as E1 : y 2 = x3 + A1 x2 + x,
E2 : y 2 = x3 + A2 x2 + x,
where A1 = 2 − 4α2 and A2 = 2 − 4(α−1 )2 . Remark 3.6. The remaining 2-isogeny with domain E is the one with kernel ⟨(0, 0)⟩. We will not keep track of this isogeny in the algebraic modeling we are going to construct. This is because when we have a chain of 2-isogenies, the isogeny with kernel ⟨(0, 0)⟩ (apart from the first step of the chain) is the backtracking isogeny, i.e., the dual isogeny to the previous step in the chain (see [35, Corollary 1]). 3.2. Renes polynomials. We are going to use Renes formulas to construct polynomials which we will use in our modeling. First, we define them and then we explain their properties. Definition 3.7. The Renes polynomials of degree 2 are the following polynomials in Z[X, Y ]: Ψ1 (X, Y ) = XY + Y 2 + 1; Ψ2 (X, Y ) = −4X 2 Y + Y 2 + 2Y + 1; Ψ3 (X, Y ) = 65536X 12 − 196608X 10 + 208896X 8 − 90112X 6 − X 4 Y + 13056X 4 + + X 2 Y − 768X 2 + 16. Proposition 3.8. Let E be a supersingular elliptic curve over Fp2 such that |E(Fp2 )| = (p ± 1)2 written in Montgomery form E : y 2 = x3 + Ax2 + x. Let φ1 : E → E1 , φ2 : E → E2 be two degree 2 isogenies (defined over Fp2 ) with kernel ̸= ⟨(0, 0)⟩. The following facts hold.
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
9
(1) Let α, α−1 ∈ Fp2 be the roots of Ψ1 (A, Y ). Then, the simplified Montgomery form of E is y 2 = x(x − α)(x − α−1 ). (2) Let γ1 , γ2 , γ3 , γ4 be the four roots of Ψ2 (α, Y ) and Ψ2 (α−1 , Y ). Then, up to relabeling, γ3 = γ1−1 , γ4 = γ2−1 and the simplified Montgomery forms of E1 and E2 are Ei : y 2 = x(x − γi )(x − γi−1 ). Proof. (1) This is clear from the discussion in §3.1. Notice that α, α−1 ∈ Fp2 by Lemma 3.3. (2) Let i ∈ {1, 2}. By Lemma 3.5, also Ei can be written in Montgomery form. Moreover, Tate’s Theorem ([45, Section 3 Theorem 1]) yields |Ei (Fq )| = |E(Fq )| = (p ± 1)2 . Thus, by Lemma 3.3 Ei can be written in simplified Montgomery form Ei : y 2 = x(x − γ)(x − γ −1 ), where γ is a root of x2 + (2 − 4β 2 )x + 1 with β ∈ {α, α−1 }. So, we have γi = −1 + 2β 2 + ci , i = 1, 2,
(4)
where the ci ’s are the two square roots of the discriminant 4β 4 − 4β 2 . If we isolate ci in (4)
and square both sides we get that γ must satisfy
−4β 2 γ + γ 2 + 2γ + 1 = 0,
(5)
that is γ is a root of Ψ2 (β, Y ). □ Proposition 3.9. Let E be a supersingular elliptic curve over Fp2 in Montgomery form. Let δ ∈ Fp2 be a root of Ψ3 (X, j(E)). Then there exists an isogeny of degree 2 (defined over Fp2 ) from y 2 = x(x − δ)(x − δ −1 ) to an elliptic curve y 2 = x3 + (2 − 4δ 2 )x2 + x with j-invariant j(E). Proof. We recall that we have six possible elliptic curves in Montgomery form with the same jinvariant of E. Indeed, their A’s are given by the relation (A2 − 3)3 . A2 − 4 Clearing the denominator in the previous equation we get that the roots of the polynomial f (Z) = (Z 2 − 4)j(E) − 256(Z 2 − 3)3 are precisely these six possible A’s. Now, let g(X, Z) = 2 − 4X 2 − Z be the polynomial obtained from Renes formulas (Lemma 3.5). In particular, for a fixed value δ, the roots of g(X, δ) are precisely the A-coefficients of the Montgomery forms of the codomain elliptic curves of the 2-isogenies from y 2 = x(x − δ)(x − δ −1 ). We consider the elimination ideal I = (g(X, Z), f (Z)) ∩ Q[X]. A computation shows that I is generated by the polynomial j(E) = 256
65536X 12 − 196608X 10 + 208896X 8 − 90112X 6 − X 4 j(E) + 13056X 4 + + X 2 j(E) − 768X 2 + 16 ∈ Z[X]. 1 f (2 − 4X 2 ). This is exactly Ψ3 (X, j(E)). Alternatively, one can check that Ψ3 (X, j(E)) = − 16 Now, let δ ∈ Fp2 be a root of Ψ3 (X, j(E)). By construction, δ satisfies f (2 − 4δ 2 ) = 0. Thus, A′ = 2 − 4δ 2 is one of the six possible Montgomery coefficients A’s coming from j(E). From what is said above, we know that there exists an isogeny of degree 2 (defined over Fp2 ) from y 2 = x(x − δ)(x − δ −1 ) to the elliptic curve y 2 = x3 + A′ x2 + x with j-invariant j(E). □
Remark 3.10. Notice that the curve y 2 = x(x−δ)(x−δ −1 ) of Proposition 3.9 is not an elliptic curve iff δ ∈ {0, ±1}. Indeed, if δ ∈ {0, ±1} then A′ ∈ {±2} which implies that j(E) is not well-defined.
10
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
3.3. The modeling. We assume the following setup. We have two supersingular elliptic curves Estart and Efinish over Fp2 in Montgomery form (with B = 1) that are connected via an isogeny φ of degree 2m (m ∈ Z≥1 ). Moreover, suppose |Estart (Fp2 )| = (p ± 1)2 , thus by Lemma 3.3, Estart can be put in simplified Montgomery form, and by Tate’s Theorem the same applies to Efinish and all elliptic curves in the chain. Finally, we assume that the first 2-isogeny (the one with domain Estart ) in the decomposition of φ is not the one associated with the 2-torsion point (0, 0). Let Astart , Afinish ∈ Fp2 be their Montgomery x2 -coefficients and j(Efinish ) the j-invariant of Efinish computed from Afinish . Using Renes polynomials, we construct a polynomial system whose solutions correspond to all possible degree 2m isogenies from Estart to an elliptic curve with j-invariant j(Efinish ). To make things more precise, we introduce the following definition which will be important also for the degree 3 case. Definition 3.11. Let d ≥ 2, m ≥ 1 be integers and let Estart and Efinish be two supersingular elliptic curves which are connected via an isogeny of degree dm . We define the set φ0
φ1
φm−1
P (d, m, Estart , j(Efinish )) = {Estart −→ E1 −→ · · · −−−→ Em | non-backtracking, ker φ0 ̸= ⟨(0, 0)⟩, deg(φi ) = d ∀i, j(Em ) = j(Efinish )}/ ∼ φ0
φ1
φ′
φm−1
φ′
(6)
φ′m−1
0 1 ′ are equivalent under ∼ if where Estart −→ E1 −→ · · · −−−→ Em and Estart −→ E1′ −→ · · · −−−→ Em ∼ = and only if for i = 1, . . . , m there exist isomorphisms ψi : Ei − → Ei′ such that the following diagram commutes φm−1 φ0 Estart E1 ··· Em−1 Em
ψ1
id
Estart
φ′0
E1′
···
ψm−1 φ′m−1 ′ Em−1
ψm ′ Em
In particular, we have j(Ei ) = j(Ei′ ) and ker(φi ) = ker(φ′i ◦ ψi ) for all i = 1, . . . , m. The set P (d, m, Estart , j(Efinish )) parametrizes all possible non-backtracking paths of degree d isogenies of length m that start from Estart and end into a supersingular elliptic curve with the same j-invariant as Efinish . We recall that by non-backtracking we mean that we do not allow two consecutive isogenies in the path to be dual to each other. The additional condition that the kernel of the first isogeny is not generated by the point (0, 0) guarantees that when the curve Estart is in Montgomery form and d = 2, then these paths can be obtained from the solutions of the following polynomial system build up from Renes polynomials. Polynomial system 2: Renes Formulas for 2-isogenies, complete Rm = Fp2 [α0 , . . . , αm−1 ] F2-Renes,m = [Ψ1 (Astart , α0 ), Ψ2 (α0 , α1 ), . . . , Ψ2 (αm−2 , αm−1 ), Ψ3 (αm−1 , j(Efinish ))] ⊆ Rm Ψ1 (Astart , α0 ) = 0 Ψ2 (α0 , α1 ) = 0 Ψ (α , α ) = 0 2 1 2 · · · Ψ2 (αm−2 , αm−1 ) = 0 Ψ3 (αm−1 , j(Efinish )) = 0.
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
11
Theorem 3.12. Let Estart , Efinish be two supersingular elliptic curves in Montgomery form over Fp2 (with the y 2 -coefficient equal to 1). Suppose that |Estart (Fp2 )| = (p ± 1)2 . Then, given m ∈ Z≥1 , there is a bijective map Θ2 : VFp2 (F2-Renes,m ) −→ P (2, m, Estart , j(Efinish )), where VFp2 (F2-Renes,m ) is the set of Fp2 -rational solutions to Polynomial system 2. Proof. First, let (α0 , . . . , αm−1 ) ∈ (Fp2 )m be a solution of Polynomial system 2. Then, by Proposition 3.8, the simplified Montgomery form of Estart is y 2 = x(x − α0 )(x − α0−1 ) and we have a degree 2 isogeny φ0 : Estart → E1 , with E1 : y 2 = x(x − α1 )(x − α1−1 ) and ker φ0 ̸= ⟨(0, 0)⟩. Applyφm−1 φ0 φ1 ing Proposition 3.8 to E1 and then recursively, we obtain a chain Estart −→ E1 −→ · · · −→ Em , where each curve in the path has simplified Montgomery form y 2 = x(x − αi )(x − αi−1 ), deg φi = 2, and ker φi ̸= ⟨(0, 0)⟩. The last condition guarantees that the path is non-backtracking. Also, by Proposition 3.9, we obtain that j(Em ) = j(Efinish ). Thus, we have constructed an element of the set P (2, m, Estart , j(Efinish )). This construction defines the desired map Θ2 . Now, we construct an inverse map Λ2 in the opposite direction. Suppose that we have a path φ of m degree 2 non-backtracking isogenies between Estart and Em with j(Efinish ) = j(Em ) and ker φ0 ̸= ⟨(0, 0)⟩: φ0
φ1
φm−1
φ : Estart −→ E1 −→ · · · −−−→ Em . We select an appropriate representative in the equivalence class of φ in P (2, m, Estart , j(Efinish )) and we use this representative to construct an element (α0 , . . . , αm−1 ) ∈ VFp2 (F2-Renes,m ). Since Estart is in Montgomery form, then ker(φ0 ) is generated by a point (α0 , 0), where α0 is one of the two distinct (since Estart is an elliptic curve) solutions of the equation Ψ1 (Astart , Y ) = Y 2 + Astart Y + 1 = 0. Notice that α0 ∈ Fp2 by Lemma 3.3. Thanks to Renes formulas (Lemma 3.5), each 2-torsion point (α, 0) defines a distinct 2-isogeny from Estart to an elliptic curve E(α) in Montgomery form defined by the coefficient A = 2 − 4α2 . In particular, the codomain curve E(α0 ) is isomorphic over Fp to the curve E1 in the fixed path φ, thus j(E1 ) = j(E(α0 )). Therefore, by composing with an isomorphism ψ1 : E1 → E(α0 ) we may replace E1 by E(α0 ), which is in Montgomery form, without changing the equivalence class of the path φ. Since the path is non-backtracking, the kernel of φ1 is generated by a point (α1 , 0), where by Proposition 3.8 α1 is a solution to the equation Ψ2 (α0 , Y ) = Y 2 + (2 − 4α02 )Y +1 = 0. We observe that α1 ∈ Fp2 since |E(α0 )(Fp2 )| = (p±1)2 by Tate’s theorem. As before, we may compose with an isomorphism ψ2 : E2 → E(α1 ) and replace E2 with a curve in Montgomery form E(α1 ) without changing the representative class of the path φ. Proceeding in this way, we obtain elements α0 , . . . , αm−1 ∈ Fp2 which satisfy the equations involving the polynomials Ψ1 and Ψ2 of Polynomial system 2. Notice that, since the path is non-backtracking, at each step we do not have to consider the isogeny with kernel generated by (0, 0). At the last step, from the condition j(Efinish ) = j(E(αm−1 )), we also obtain that αm−1 is a solution to the equation Ψ3 (X, j(Efinish )) = 0 by Proposition 3.9. Therefore, (α0 , . . . , αm−1 ) is a solution of Polynomial system 2. In particular, this construction defines a map Λ2 : P (2, m, Estart , j(Efinish )) −→ VFp2 (F2-Renes,m ) which is the inverse of the map Θ2 defined above, hence Θ2 is bijective. □ Remark 3.13 (Comparison with modular polynomials). We point out some distinctions between the approach with Renes polynomials and with modular polynomials. (1) Once we have a solution of Polynomial system 2, we are able to directly recover the explicit curves (in simplified Montgomery form) that are in the path of the 2m -isogeny, while this is
12
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
not immediate with modular polynomials. Moreover, we can also give a precise description of the 2-isogenies in the path. Those formulas can be found in [35, Proposition 2]. (2) It is not true in this setting that there exists a 2-isogeny between two elliptic curves in simplified Montgomery form with parameters α1 and α2 if and only if Ψ2 (α1 , α2 ) = 0. This is due to the fact that Renes polynomials do not take into account the different representations of the curves, which may have different Montgomery forms isomorphic to each other. Moreover, Renes polynomials do not consider the backtracking isogeny, associated to the 2-torsion point (0, 0). Indeed, Ψ2 (X, Y ) is not a symmetric polynomial. 3.4. The (compact) modeling. From a computational point of view, the presence of the degree 12 polynomial Ψ3 in Polynomial System 2 makes it harder to solve. To fix this issue, we consider 2 6 systems where the last equation is replaced by (2 − 4αm−1 ) − A = 0, where A is one of the 6 possible roots of the polynomial that codifies all the possible A’s of a curve in Montgomery form with fixed j-invariant j(Efinish ). Explicitly, we precompute those A’s as the roots of 256(X 2 − 3)3 − j(Efinish )(X 2 − 4) ∈ Fp2 [X] and we plug them into the polynomial Ψ4 = −4X 2 − Y + 2 ∈ Z[X]. We obtain 6 equations Ψ4 (αm−1 , A) = 0, which give rise to 6 new polynomial systems of the following form. Polynomial system 3: Renes Formulas for 2-isogenies, compact Rm = Fp2 [α0 , . . . , αm−1 ] R2,m = [Ψ1 (Astart , α0 ), Ψ2 (α0 , α1 ), . . . , Ψ2 (αm−2 , αm−1 ), Ψ4 (αm−1 , A)] ⊆ Rm Ψ1 (Astart , α0 ) = 0 Ψ2 (α0 , α1 ) = 0 Ψ (α , α ) = 0 2 1 2 ··· Ψ2 (αm−2 , αm−1 ) = 0 Ψ4 (αm−1 , A) = 0. Now, the degree of the last polynomial is 2 instead of 12. Moreover, only one of these 6 systems will have a solution, but the computations can be parallelized and, once a solution is found, all other computations can be aborted. Notice that, since we already have Afinish and we know that −Afinish is also an admissible A, to find the other A’s we can now find the roots of a polynomial of degree 4. This means that the pre-computation of the A’s is computationally irrelevant with respect to the computation of a Gröbner basis. For these reasons, we will focus on Polynomial System 3 rather than Polynomial System 2. We postpone to Section 5 and Section 6 an analysis of its algebraic properties and a report on some computational experiments. 4. Algebraic Modeling with Renes Polynomials in degree 3 In this section, we consider chain of isogenies of degree 3. Given a supersingular elliptic curve E we have four isogenies of degree 3 with domain the curve E, and the kernel of a 3-isogeny is a subgroup of E[3] of order 3. In [35], Renes gives a description for degree 3-isogenies similar to
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
13
the degree 2 in the previous subsection. We use it to construct polynomials and build an algebraic modeling for SIP. 4.1. Triangular curves and Renes formulas. A supersingular elliptic curve E is in triangular form if it is given by an equation E : y 2 + axy + by = x3 , for some a, b ∈ Fp2 . If b is a cube in Fp2 , then writing b = β 3 for some β ∈ Fp2 , we obtain b = 1 through the transformation (x, y) 7→ (x/β 2 , y/β 3 ). For simplicity, in the following, we will always assume that the elliptic curve admits a triangular form with b = 1. We recall that in this case the condition of being non-singular is equivalent to a3 ̸= 27. As for Montgomery curves, not every supersingular elliptic curve can be put into triangular form. However, if the curve E/Fp2 contains a rational point of order 3, then it can be written in triangular form (see [6, Theorem 5.2]). We point out that when an elliptic curve is in triangular form, the point (0, 0) has order 3. The following lemma, whose proof is analogous to the proof of Lemma 3.3, gives a sufficient criterion for the rationality of points of order 3. Lemma 4.1. Let E be a supersingular elliptic curve defined over Fp2 . Assume that |E(Fp2 )| = (p − 1)2 if p ≡ 1 mod 3 and |E(Fp2 )| = (p + 1)2 if p ≡ 2 mod 3. Then E[3] ⊆ E(Fp2 ), i.e., the 3-torsion points of E are Fp2 -rational. Remark 4.2. Notice that, if we are in a case for a curve E as in Lemma 4.1 where p ≡ 1 mod 3 but |E(Fp2 )| = (p + 1)2 (resp. p ≡ 2 mod 3 but |E(Fp2 )| = (p − 1)2 ), we can pass to a twist Eqt of E such that |Eqt (Fp2 )| = (p − 1)2 (resp. |Eqt (Fp2 )| = (p + 1)2 ) and work with Eqt . Therefore, up to a twist, we can always apply Lemma 4.1. As for the degree 2 case, if E is a supersingular elliptic curve in triangular form and φ : E → E ′ is a degree 3 isogeny with ker φ ̸= ⟨(0, 0)⟩, then also E ′ can be put in triangular form and the Fp2 -rationality of the 3-torsion points is preserved. More precisely, the 3-isogenies with domain E can be explicitly described by Renes formulas as follows (cf. [35, Proposition 4, Corollary 3]). Lemma 4.3 (Renes formulas, degree 3). Given a supersingular elliptic curve E : y 2 + axy + y = x3 in triangular form and (xP , yP ) ∈ E(Fp2 ) a 3-torsion point distinct from (0, 0), then we have a 3-isogeny φ : E → E ′ , where E ′ : y 2 + Axy + y = x3 with A = −3(2 + axP ). Moreover, the dual isogeny φ̂ : E ′ → E is the one with kernel ⟨(0, 0)⟩. 4.2. Renes polynomials. We are going to use Renes formulas to construct polynomials which we will use in our modeling. First, we define them and then we explain their properties. Definition 4.4. The Renes polynomials of degree 3 are the following polynomials in Z[X, Y ]: Γ1 (X, Y ) = X 3 Y 2 + 3X 3 Y + 9X 3 − Y 3 − 18Y 2 − 108Y − 216; Γ2 (X, Y ) = X 12 − 72X 9 + 1728X 6 − X 3 Y − 13824X 3 + 27Y. Proposition 4.5. Let E be a supersingular elliptic curve over Fp2 written in triangular form as y 2 + axy + y = x3 . Assume that |E(Fp2 )| = (p − 1)2 if p ≡ 1 mod 3 and |E(Fp2 )| = (p + 1)2 if p ≡ 2 mod 3. For i ∈ {1, 2, 3}, let φi : E → Ei be the three degree 3 isogenies (defined over Fp2 ) with kernel ̸= ⟨(0, 0)⟩. Let γ1 , γ2 , γ3 ∈ Fp2 be the roots of Γ1 (a, Y ). Then, (up to relabeling) the triangular form of Ei is y 2 + γi xy + y = x3 .
14
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
Proof. The assumption on the number of rational points of E guarantees that the 3-torsion points of E are rational by Lemma 4.1. Then, by Lemma 4.3 each 3-torsion point (xi , yi ) ̸= (0, 0) gives a degree 3 isogeny to an elliptic curve in triangular form E ′ : y 2 + γi xy + y = x3 with γi = −3(2 + axi ). Thus, it is enough to prove that γ1 , γ2 , γ3 are precisely the three roots of Γ1 (a, Y ). First, we recall that the x-coordinates of the 3-torsion points of E are the roots of the 3-division polynomial ψ3 (a, Z) = 3Z 4 + a2 Z 3 + 3aZ 2 + 3Z. Notice, that ψ3 (a, 0) = 0, since (0, 0) is always a 3-torsion point. Since we are not interested in the isogeny with kernel ⟨(0, 0)⟩, we divide by Z and consider the polynomial with integer coefficients f3 (X, Z) = 3Z 3 + Z 2 X 2 + 3XZ + 3. ψ f3 (a, Z) are the x-coordinates of the 3-torsion points of E distinct from (0, 0). We also The roots of ψ introduce the polynomial θ(X, Y, Z) = 3XZ + Y + 6 ∈ Z[X, Y, Z] f3 (a, Z) the root of θ(a, Y, z) is one of γ1 , γ2 , γ3 by with the property that for any root z of ψ Lemma 4.3. Now, we consider the elimination ideal f3 (X, Z), θ(X, Y, Z)) ∩ Q[X, Y ]. I = (ψ A computation shows that the ideal I is principally generated by the polynomial Γ1 (X, Y ) = X 3 Y 2 + 3X 3 Y + 9X 3 − Y 3 − 18Y 2 − 108Y − 216. Thus, the roots of Γ1 (a, Y ) are precisely γ1 , γ2 , γ3 as required. □ Proposition 4.6. Let E be a supersingular elliptic curve over Fp2 in triangular form. Let δ ∈ Fp2 be a root of Γ2 (X, j(E)), then the elliptic curve y 2 + δxy + y = x3 has j-invariant j(E). Proof. Let y 2 + axy + y = x3 be the triangular form of E with a ∈ Fp2 , a3 ̸= 27. We recall that the j-invariant of E is given by the formula a3 (a3 − 24)3 . a3 − 27 Thus, there are 12 possible a’s giving an elliptic curve in triangular form with j-invariant j(E). By clearing denominators, these can be expressed as the roots of the polynomial Γ2 (X, j(E)), where j(E) =
Γ2 (X, Y ) = X 12 − 72X 9 + 1728X 6 − X 3 Y − 13824X 3 + 27Y ∈ Z[X, Y ]. □ 4.3. The modeling. We assume the following setup. We have two supersingular elliptic curves Estart and Efinish over Fp2 in triangular form that are connected via an isogeny φ of degree 3m (m ∈ Z≥1 ) and suppose that the first 3-isogeny in the decomposition of φ has kernel ̸= ⟨(0, 0)⟩. We assume further that |Estart (Fp2 )| = (p − 1)2 if p ≡ 1 mod 3 and |Estart (Fp2 )| = (p + 1)2 if p ≡ 2 mod 3. Let astart be the xy-coefficient of the triangular form of Estart and let j(Efinish ) be the j-invariant of Efinish . Using Renes polynomials (Definition 4.4), we construct a polynomial system whose solutions represent the a’s of the triangular forms of the elliptic curves in the path that connects Estart and Efinish . Notice that Tate’s theorem ensures that all curves in the path will have the same number of rational points as Estart , and thus can be put in triangular form as well by Lemma 4.1.
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
15
Polynomial system 4: Renes Formulas for 3-isogenies, complete Um = Fp2 [a1 , . . . , am ] F3-Renes,m = [Γ1 (astart , a1 ), Γ1 (a1 , a2 ), · · · , Γ1 (am−1 , am ), Γ2 (am , j(Efinish ))] ⊆ Um Γ1 (astart , a1 ) = 0 Γ1 (a1 , a2 ) = 0 ······ Γ1 (am−2 , am−1 ) = 0 Γ1 (am−1 , am ) = 0 Γ2 (am , j(Efinish )) = 0 The solutions of Polynomial system 4 are in bijection with the set P (3, m, Estart , j(Efinish )) of Definition 3.11 which parametrizes all possible non-backtracking paths of degree 3 isogenies of length m that start from Estart and ends into a supersingular elliptic curve with the same j-invariant as Efinish . We state this in the next theorem. The proof is analogous to the proof of Theorem 3.12, where Lemma 4.1, Lemma 4.3, Proposition 4.5, and Proposition 4.6 shall be used. Theorem 4.7. Let Estart , Efinish be two supersingular elliptic curves in triangular form over Fp2 (with the y-coefficient equal to 1). Assume that |Estart (Fp2 )| = (p − 1)2 if p ≡ 1 mod 3 and |Estart (Fp2 )| = (p + 1)2 if p ≡ 2 mod 3. Then, given m ∈ Z≥1 , there is a one to one correspondence between the set of Fp2 -rational solutions to Polynomial system 4 and the set P (3, m, Estart , j(Efinish )). As for the degree 2 case, this complete polynomial system is difficult to solve with Gröbner bases because the polynomial Γ2 (am , j(Efinish )) has degree 12. So, as before, we replace the complete system with 12 compact ones, replacing the last equation with Γ1 (am−1 , a), where the a’s are the roots of the polynomial Γ2 (X, j(Efinish )). We obtain the following systems, which we will focus our analysis on. Polynomial system 5: Renes Formulas for 3-isogenies, compact Um−1 = Fp2 [a1 , . . . , am−1 ] R3,m = [Γ1 (astart , a1 ), Γ1 (a1 , a2 ), · · · , Γ1 (am−2 , am−1 ), Γ1 (am−1 , a)] ⊆ Um−1 Γ1 (astart , a1 ) = 0 Γ1 (a1 , a2 ) = 0 ······ Γ1 (am−2 , am−1 ) = 0 Γ (a 1 m−1 , a) = 0 5. Algebraic Analysis In this section, we study some algebraic properties of the systems introduced: • the system of modular polynomials Mℓ,m , where ℓ ̸= p is a prime number (Polynomial system 1); • the system of (compact) Renes polynomials R2,m−1 in degree 2 (Polynomial System 3); • the system of (compact) Renes polynomials R3,m in degree 3 (Polynomial System 5).
16
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
Notice, that for degree 2 we consider the system R2,m−1 parametrizing paths of length m − 1 since it has m − 1 variables as the system R3,m of degree 3 (which parametrizes paths of length m). First, we prove that the systems are zero-dimensional, i.e., they admit a finite number of solutions over the algebraic closure Fp . For modular polynomials, this was already observed in [44]. First, we need the following lemma. Lemma 5.1. Let S = K[x1 , . . . , xn ] be a polynomial ring over a field K and let I = (f1 , . . . , fn+1 ) ⊆ S be an ideal. If, up to reordering the generators of I, there exists a term order < on S such that LT< (f1 ), . . . , LT< (fn ) are coprime and of degree ≥ 1, then I is zero-dimensional and f1 , . . . , fn is a regular sequence of (maximal) length n in I. Proof. Since LT< (f1 ), . . . , LT< (fn ) are coprime, the polynomials f1 , . . . , fn form a reduced Gröbner basis for the ideal I˜ = (f1 , . . . , fn ). Moreover, since LT< (f1 ), . . . , LT< (fn ) are precisely n and of deg(LT (f )) degree ≥ 1, there exists a permutation σ ∈ Sn such that LT< (fi ) = xσ(i) < i for all i = 1, . . . , n. So, the ideal I˜ is zero-dimensional and LT< (f1 ), . . . , LT< (fn ) is a regular sequence of maximal ˜ Macaulay Basis Theorem (see e.g. [36, Theorem 1.5.7]) yields that the ideal I˜ is length n in I. zero-dimensional, hence I is zero-dimensional as well. Finally, by [37, Tutorial 54], we obtain that f1 , . . . , fn is a regular sequence of maximal length n in I. □ Proposition 5.2. Let m ≥ 2. The ideals (Mℓ,m ), (R2,m−1 ), and (R3,m ) are zero-dimensional and contain a regular sequence of (maximal) length m − 1. Proof. For every statement, we want to use Lemma 5.1 to conclude. For (Mℓ,m ), we consider a Lex term order < with jm−1 > jm−2 > · · · > j1 . Then, the leading terms of the first m − 1 polynomials ℓ+1 , which are coprime and of degree ≥ 1. For (R2,m−1 ), we consider of Mℓ,m are j1ℓ+1 , j2ℓ+1 , . . . , jm−1 a Lex term order < with αm−2 > αm−3 > · · · > α0 . Then, the leading terms of the first m − 1 2 polynomials of R2,m−1 are α02 , α12 , . . . , αm−2 , which are coprime and of degree ≥ 1. For (R3,m ) we consider a Lex term order < with am−1 > am−2 > · · · > a1 . Then, the leading terms of the first m − 1 polynomials of R3,m are a31 , a32 , . . . , a3m−1 , which are coprime and of degree ≥ 1. □ The notion of degree of regularity was introduced in [4] as a way to measure the complexity of solving a polynomial system via linear-algebra based algorithms. Indeed, under suitable assumptions the degree of regularity provides an upper bound on the solving degree [39]. In a nutshell, given a polynomial system F = {f1 , . . . , fs } the degree of regularity dreg is the minimum integer d such that the homogeneous degree d piece of the ideal (f1top , . . . , fstop ) coincides with the polynomial ring in degree d. If this minimum does not exists, i.e., when the ideal (f1top , . . . , fstop ) is not zerodimensional, then the degree of regularity is not defined or is set to be ∞, depending on the convention. Thus, when (f1top , . . . , fstop ) is not zero-dimensional the degree of regularity does not provide an immediate insight on the complexity of solving the related system. We prove that this is the case for the systems under study. More precisely, in Proposition 5.4 we compute the Krull dimension of the ideal generated by the top part of the system. We need a technical lemma. Lemma 5.3. Let K be a field, and let S = K[x1 , . . . , xn ] be a polynomial ring. We consider the monomial ideal I = (x1 , x1 x2 , . . . , xn−1 xn , xn ). Then, we have ( n−2 if n even 2 dim(S/I) = n−1 if n odd. 2
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
17
Proof. If n = 1 or 2, then dim(S/I) = dim(K) = 0, since K is a field. Let n ≥ 3, then dim(S/I) = dim(K[x2 , . . . , xn−1 ]/(x2 x3 , . . . , xn−2 xn−1 )). Thus, for computing the Krull dimension we may replace the polynomial ring by S = K[y1 , . . . , yt ] and the ideal by I = (y1 y2 , . . . , yt−1 yt ). Now, the dimension of I can be computed as dim S/I = t − min{ht(P ) | P ∈ Min(I)}, where Min(I) is the set of minimal primes of I. Now, let t = 2k be even (k ∈ Z≥1 ). We claim that the ideal P = (y2 , y4 , . . . , y2k ) of height k is the minimal prime ideal over I that realizes the minimum above. By [27, Theorem 1.3.1, Corollary 1.3.4] an irredundant presentation of I is given by \ I= Vi , i=1,...,s
where each Vi is a (prime) ideal of variables with ht(Vi ) = µ(Vi ). Moreover, since I is squarefree (hence radical), we can write \ I= P. P ∈Min(I)
For any i = 1, . . . , 2k − 1, we have yi | yi yi+1 and yi+1 | yi yi+1 and either i or i + 1 is even, thus the prime ideal P contains I. We claim that it does not exist a minimal prime ideal P ′ of I such that ht(P ′ ) < ht(P). Once the claim is proved, then we are done since P will be minimal and of the smallest possible height. Assume by contradiction, that such a P ′ exists. Thanks to the decompositions above, we have \ \ I= Vi = P. i=1,...,s
P ∈Min(I)
By properties of the irredundant decomposition (see [27, Lemma 1.3.5]), for every P ∈ Min(I) there exists i ∈ {1, . . . , s} such that P = Vi . Then, for some h ∈ {1, . . . , s}, we have P ′ = Vh . In particular, P ′ is an ideal of variables, so µ(P ′ ) = ht(P ′ ) < k. This tells us that there exist two consecutive variables yc , yc+1 (for some c ∈ {1, . . . , 2k − 1}) such that yc , yc+1 ̸∈ P ′ . But yc yc+1 ∈ I, so I ̸⊆ P ′ , and this is a contradiction. So, the Krull dimension of I˜ is t − k = 2k − k = k = n−2 2 . For t = 2k − 1 odd the argument is the same but P = (y2 , y4 , . . . , y2k−2 ) is the minimal prime ideal which realizes the height. □ top top Proposition 5.4. Let m ≥ 2. The (Krull) dimension of the ideals (Mtop ℓ,m ),(R2,m−1 ) and (R3,m ) coincides and it is equal to ( m−2 if m even 2 m−3 if m odd. 2
In particular, if m ≥ 4, these ideals are not zero-dimensional. Proof. For every statement, we use Lemma 5.3 with n = m − 1 to conclude. For (Mtop ℓ,m ), we have top ℓ+1 ℓ ℓ ℓ+1 ℓ ℓ that (Mℓ,m ) = (j1 , j1 j2 , . . . , jm−2 jm−1 , jm−1 ). Passing to the radical the Krull dimension does q not change and (Mtop ) = (j1 , j1 j2 , . . . , jm−2 jm−1 , jm−1 ) has the shape of Lemma 5.3. Simiq ℓ,m q top larly, we have that (R2,m−1 ) = (α0 , α0 α1 , . . . , αm−3 αm−2 , αm−2 ), and (Rtop 3,m ) = (a1 , a1 a2 , . . . , am−2 am−1 , am−1 ). □
18
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
Another consequence of Proposition 5.4 is that when m ≥ 4 the polynomial systems are not semi-regular [4, 7, 34]. top top Corollary 5.5. For every m ≥ 4, we have that Mtop ℓ,m , R2,m−1 and R3,m are not semi-regular sequences.
Another invariant which can be used as a proxy for the solving degree is the Castelnuovo–Mumford regularity. Indeed, when the ideal is in generic coordinates in the sense of Bayer and Stillman [5], then the regularity of the ideal generated by the homogenized polynomials of the system is greater or equal than the solving degree of the system by [12]. On the other hand, in Proposition 5.7, we prove that the systems Mℓ,m , R2,m−1 and R3,m are not in generic coordinates. For the convenience of the reader, we recall here the relevant definitions and notations. Let K be a field and let S = K[x1 , . . . , xn ] be a polynomial ring. For a polynomial f ∈ S, we denote by f h ∈ R = S[t] its homogenization with respect to an extra variable t, that is x xn 1 h deg(f ) ,..., . f =t ·f t t For a list of polynomials F = [f1 , . . . , fs ] in S, we denote by F h = [f1h , . . . , fsh ] the list of the homogenized polynomials in R. If I ⊆ S is an ideal, we denote by I h the ideal generated by all the homogenizations of elements in I, that is I h = (f h | f ∈ I). Clearly, we have (F h ) ⊆ (F)h , but the inclusion may be strict. Given a homogeneous ideal J of R, the saturation of J with respect to the irrelevant maximal ideal m = (x1 , . . . , xn , t) of R is [ [ J sat = {f ∈ R | f m ∈ J ∀m ∈ Rd } = (J : md ). d≥0
d≥0
We stress that the condition f m ∈ J ∀m ∈ Rd can be checked only on the monomials of Rd , since they form a K-basis for Rd and J is an ideal. Moreover, we always have that J ⊆ J sat . Now, let J = JK[x1 , . . . , xn , t] be the extension of the ideal J over the algebraic closure K of K. We say sat that J is in generic coordinates over K if |Z+ (J)| < ∞ and either |Z+ (J)| = 0 or t ∤ 0 modulo J . Lemma 5.6. Let K be an algebraically closed field and let S = K[x1 , . . . , xn ] be a polynomial ring. Let F = [f1 , . . . , fm ] be a list of non-homogeneous polynomials such that |Z(F)| = 1. Assume that m S there exists i ∈ {1, . . . , n} such that for all integers a ≥ 1 we have xai ̸∈ Supp(F h ) = Supp(fch ). c=1
Then, the ideal (F h ) is not in generic coordinates over K. Proof. Let Z(F) = {(a1 , . . . , an )} ⊆ K n . Thanks to the Shape Lemma (see e.g. [12]), we get that LexGB((F)) = [x1 − a1 , . . . , xn − an ]. Since (F ) is zero-dimensional, [x1 − a1 , . . . , xn − an ] is also the reduced Gröbner basis with respect to DegRevLex. Thanks to [37, Proposition 4.3.21], the homogenized ideal (F)h is generated by the homogenization of this basis, that is (F)h = (x1 − a1 t, . . . , xn − an t) ⊆ S[t] = R. From now on, we equip R with the DegRevLex term order with x1 > · · · > xn > t. Moreover, we have that (F h ) ⊆ (F h )sat ⊆ (F)h , where the former follows from the definition of saturation and the latter from the fact that [ [ (F h )sat = ((F h ) : md ), (F)h = ((F h ) : (t)d ), and (t) ⊆ m. d≥0
d≥0
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
19
Now, we claim that t | 0 modulo (F h )sat . By assumption, we can fix i ∈ {1, . . S . , n} such that a h h h xi ̸∈ Supp(F ) ∀a ∈ Z≥1 and we know that xi −ai t ∈ (F) . So, again since (F ) = ((F h ) : (t)d ), d≥0
there exists d˜ ∈ Z≥1 such that ˜
(xi − ai t) · td ∈ (F h ) ⊆ (F h )sat . Note that d˜ cannot be 0. In fact, since by assumption xai ̸∈ Supp(F h ) for all a ∈ Z≥1 , then xi ∈ Supp(xi − ai t) cannot be written as a polynomial combination of the generators F h . If we prove that xi − ai t ̸∈ (F h )sat , the claim follows. Suppose by contradiction that xi − ai t ∈ ′ (F h )sat . Then, by definition of saturation, there exists d′ ∈ Z≥0 such that xi − ai t ∈ [(F h ) : md ]. ′ ′ Now, xdi ∈ md , so ′ ′ ′ f = (xi − ai t) · xdi = xdi +1 − ai xdi t ∈ (F h ). ′
But, since by assumption xai ̸∈ Supp(F h ) for all a ∈ Z≥1 , again xdi +1 ∈ Supp(f ) cannot be written as a polynomial combination of the generators F h . Therefore f ̸∈ (F h ) and we get a contradiction, which proves the claim. Finally, since (a1 , . . . , an ) ∈ Z(F ), we get that [a1 : · · · : an : 1] ∈ Z+ (F h ), so |Z+ (F h )| > 0. This concludes the proof. □ Proposition 5.7. Let m ≥ 4 and let F = Mℓ,m , R2,m−1 , or R3,m . If |Z(F)| = 1, then (F h ) is not in generic coordinates over Fp . Proof. Let F = Mℓ,m . Since m ≥ 4, we have that j2b ̸∈ Supp(Mhℓ,m ) for all b ∈ Z≥1 . So, we conclude using Lemma 5.6. Similarly, for R2,m−1 , it holds α1b ̸∈ Supp(Mh2,m−1 ) for all b ∈ Z≥1 and for R3,m it holds ab2 ̸∈ Supp(Mh3,m ) for all b ∈ Z≥1 , so in both cases we conclude using again Lemma 5.6. □ Remark 5.8. If m ≥ 6 for F = Mℓ,m , R2,m−1 , or R3,m , it is easier to check that (F h ) is not in generic coordinates over Fp . In fact, one can show that |Z+ (F h )| = ∞. Indeed, [0 : v1 : 0 : · · · : 0 : v2 : 0] ∈ Z+ (F h ) for all v1 ,v2 ∈ Fp linearly independent. 6. Experimental Results We solved the polynomial systems arising from the previous modelings using Gröbner bases in order to compare the modeling based on Renes polynomials with that based on modular polynomials. All computations were performed using Magma V2.28-13 [8], on a Dell Inc. Precision 7875 Tower, with 64 GB of RAM and processor AMD ®Ryzen threadripper pro 7975wx 32-cores x 64. We constructed the test examples as follows. Let d = 2, 3 be the degree. We selected a random supersingular elliptic curve Estart in Montgomery form (for degree d = 2) or triangular form (for degree d = 3) and we constructed a non-backtracking path of length m of isogenies obtaining the curve Efinish . Then, we built the system Md,m of modular polynomials (Polynomial system 1) and Rd,m of Renes polynomials (Polynomial System 3 and Polynomial System 5) to recover the path from Estart to Efinish . These systems were solved using Magma’s implementation of F4 [23]. We recorded the CPU time and the maximal degree reached during the Gröbner basis computation (used as a proxy for the solving degree). We repeated these computations for nine different values of the underlying prime p, ranging from 10 to 32 bits. For each set of parameters, we performed 10 tests. In Table 1 and Table 2, we report the results for degrees 2 and 3, respectively. The results show that the solving degree is consistently smaller for Renes polynomials than for modular polynomials. Moreover, the average solving times
20
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
are two to three orders of magnitude lower for Renes polynomials. This allows us to solve paths of isogenies of length up to 16 in degree 2 for small primes, whereas we are limited to length 12 when using modular polynomials. A similar trend is observed in degree 3. Remark 6.1. To solve longer paths of degree 3 isogenies described by the modular polynomial systems M3,m , Takahashi et al. [44] split the system into two halves and compute a Gröbner basis for each of them. Then, by eliminating variables, they find the solutions. This technique can also be applied to the polynomial systems R2,m and R3,m with Renes polynomials, allowing one to recover longer isogeny paths. However, to enable a clearer comparison of the systems, we chose not to apply this splitting technique to any of the computations performed in this paper.
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
m
tm(M2,m )
6 7 8 9 10 11 12 13 14 15 16 17
0.02 0.514 1.722 66.563 78.454 3040.88 3359.307 > 7 hrs
tm(R2,m ) sd(M2,m ) p = 587417, 20 bits 0.003 0.018 0.09 0.298 2.008 15.958 50.588 104.499 434.435 7632.326 23416.61 > 7 hrs
6 7 7 8 8 9 9
sd(R2,m )
m
tm(M2,m )
4 5 5 5 5 5 5 6 6 6 6
6 7 8 9 10 11 12 13 14 15 16 17
0.02 0.671 2.612 135.981 179.822 10055.526 11223.916 > 7 hrs
p = 15739441, 24 bits 6 7 8 9 10 11 12 13 14 15 16 17
0.02 0.502 1.738 67.766 76.685 2710.243 2618.765 > 7 hrs
0.001 0.018 0.09 0.309 2.019 15.68 50.162 104.273 437.867 7582.87 23514.02 > 7 hrs
6 7 7 8 8 9 9
0.022 0.704 2.674 129.268 168.687 9739.063 11001.887 > 7 hrs
0.003 0.02 0.102 0.371 2.923 27.347 95.651 207.348 1000.487 > 7 hrs
6 7 7 8 8 9 9
0.002 0.02 0.102 0.375 3.009 27.815 96.897 213.71 1016.976 > 7 hrs
sd(R2,m )
6 7 7 8 8 9 9
4 5 5 5 5 5 5 6 6
p = 16541149, 24 bits 4 5 5 5 5 5 5 6 6 6 6
6 7 8 9 10 11 12 13 14 15 16 17
p = 266545607, 28 bits 6 7 8 9 10 11 12 13 14 15
tm(R2,m ) sd(M2,m ) p = 919447, 20 bits
21
0.02 0.506 1.716 67.375 77.189 2692.042 2610.953 > 7 hrs
0.001 0.019 0.08 0.276 1.951 15.635 50.164 103.944 438.755 7703.542 > 7 hrs
6 7 7 8 8 9 9
4 5 5 5 5 5 5 6 6 6
p = 2757059413, 32 bits 4 5 5 5 5 5 5 6 6
6 7 8 9 10 11 12 13 14 15
0.086 2.333 8.678 390.104 476.839 21743.386 22894.691 > 7 hrs
0.01 0.06 0.387 1.361 10.147 86.571 284.438 612.507 2762.891 > 7 hrs
6 7 7 8 8 9 9
Table 1. Timings and solving degrees for polynomial systems modeling a SIP of degree 2m . The values tm(M2,m ) and tm(R2,m ) record the average time (in seconds) of solving the polynomial systems M2,m (modular polynomials) and R2,m (Renes polynomials) modeling a SIP of degree 2m ; sd(M2,m ) and sd(R2,m ) are the highest step degrees obtained during the computation by using Magma F4 implementation.
4 5 5 5 5 5 5 6 6
22
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
m
tm(M3,m )
6 7 8 9 10 11 12
0.901 76.149 1887.466 > 7 hrs
tm(R3,m ) sd(M3,m ) p = 919447, 20 bits 0.074 1.345 30.398 42.104 2620.534 > 7 hrs
8 10 10
sd(R3,m )
m
tm(M3,m ) tm(R3,m ) sd(M3,m ) p = 15739441, 24 bits
6 7 7 8 8
6 7 8 9 10 11 12
0.648 43.406 724.222 11580.257 m>9
p = 16541149, 24 bits 6 7 8 9 10 11 12
0.652 43.066 726.928 11609.202 > 7 hrs
0.06 0.912 17.443 202.294 1001.411 17303.164 > 7 hrs
8 10 10 11
0.897 75.404 1766.141 > 7 hrs
0.073 1.302 30.031 419.066 2579.288 > 7 hrs
8 10 10
8 10 10 11
6 7 7 8 8 9
p = 12239911, 24 bits 6 7 7 8 8 9
6 7 8 9 10 11 12
0.906 74.625 1721.217 > 7 hrs
p = 266545607, 28 bits 6 7 8 9 10 11
0.06 0.916 17.511 203.132 1000.555 17300.334 > 7 hrs
sd(R3,m )
0.074 1.304 29.82 411.02 2531.694 > 7 hrs
8 10 10
6 7 7 8 8
p = 2757059413, 32 bits 6 7 7 8 8
6 7 8 9 10 11
2.968 241.397 4705.333 > 7 hrs
0.283 4.486 95.73 1225.204 6568.001 > 7 hrs
8 10 10
6 7 7 8 8
Table 2. Timings and solving degrees for polynomial systems modeling a SIP of degree 3m . The values tm(M3,m ) and tm(R3,m ) record the average time (in seconds) of solving the polynomial systems M3,m (modular polynomials) and R3,m (Renes polynomials) modeling a SIP of degree 3m . sd(M3,m ) and sd(R3,m ) are the highest step degrees obtained during the computation by using Magma F4 implementation.
References [1] G. Adj, O. Ahmadi, and A. Menezes, On isogeny graphs of supersingular elliptic curves over finite fields, Finite Fields Appl., 55 (2019), pp. 268–283. 8 [2] M. R. Albrecht, C. Cid, J.-C. Faugère, R. Fitzpatrick, and L. Perret, Algebraic Algorithms for LWE Problems, ACM Commun. Comput. Algebra, 49 (2015), p. 62. 1 [3] S. Arora and R. Ge, New Algorithms for Learning in Presence of Errors, in Automata, Languages and Programming, L. Aceto, M. Henzinger, and J. Sgall, eds., Berlin, Heidelberg, 2011, Springer Berlin Heidelberg, pp. 403–415. 1 [4] M. Bardet, J. C. Faugère, and B. Salvy, On the complexity of Gröbner basis computation of semi-regular overdetermined algebraic equations, in ICPPSS International Conference on Polynomial System Solving, 2004. 2, 5, 16, 18 [5] D. Bayer and M. Stillman, A criterion for detecting m-regularity, Invent. Math., 87 (1987), pp. 1–11. 18 [6] D. J. Bernstein, C. Chuengsatiansup, D. Kohel, and T. Lange, Twisted Hessian curves, in Progress in cryptology—LATINCRYPT 2015, vol. 9230 of Lecture Notes in Comput. Sci., Springer, Cham, 2015, pp. 269– 294. 13
ALGEBRAIC MODELINGS OF THE SUPERSINGULAR ISOGENY PROBLEM
23
[7] M. Bigdeli, E. De Negri, M. M. Dizdarevic, E. Gorla, R. Minko, and S. Tsakou, Semi-regular sequences and other random systems of equations, in Women in numbers Europe III—research directions in number theory, vol. 24 of Assoc. Women Math. Ser., Springer, Cham, [2021] ©2021, pp. 75–114. 18 [8] W. Bosma, J. Cannon, and C. Playoust, The Magma Algebra System. I. The User Language, vol. 24, 1997, pp. 235–265. Computational algebra and number theory (London, 1993). 19 [9] B. Buchberger, Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal, PhD thesis, University of Innsbruck, 1965. 4 [10] J. Burdges and L. De Feo, Delay Encryption, in Advances in cryptology—EUROCRYPT 2021. Part I, vol. 12696 of Lecture Notes in Comput. Sci., Springer, Cham, [2021] ©2021, pp. 302–326. 2, 7, 8 [11] A. Caminata, R. Cartor, A. Meneghetti, R. Mora, and A. Pellegrini, Quadratic Modelings of Syndrome Decoding, in Post-quantum cryptography. Part I, vol. 15577 of Lecture Notes in Comput. Sci., Springer, Cham, [2025] ©2025, pp. 35–70. 1 [12] A. Caminata and E. Gorla, Solving multivariate polynomial systems and an invariant from commutative algebra, in Arithmetic of finite fields, vol. 12542 of Lecture Notes in Comput. Sci., Springer, Cham, [2021] ©2021, pp. 3–36. 2, 4, 5, 18 [13] , Solving degree, last fall degree, and related invariants, J. Symbolic Comput., 114 (2023), pp. 322–335. 5 [14] D. Charles and K. Lauter, Computing Modular Polynomials, LMS J. Comput. Math., 8 (2005), pp. 195–204. 6 [15] M. Corte-Real Santos, C. Costello, and J. Shi, Accelerating the Delfs-Galbraith Algorithm with Fast Subfield Root Detection, in Annual International Cryptology Conference, Springer, 2022, pp. 285–314. 1 [16] C. Costello and H. Hisil, A simple and compact algorithm for SIDH with arbitrary degree isogenies, in Advances in cryptology—ASIACRYPT 2017. Part II, vol. 10625 of Lecture Notes in Comput. Sci., Springer, Cham, 2017, pp. 303–329. 2, 7 [17] C. Costello and B. Smith, The Supersingular Isogeny Problem in Genus 2 and Beyond, in Post-quantum cryptography, vol. 12100 of Lecture Notes in Comput. Sci., Springer, Cham, [2020] ©2020, pp. 151–168. 1 [18] N. Courtois, A. Klimov, J. Patarin, and A. Shamir, Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations, in Advances in cryptology—EUROCRYPT 2000 (Bruges), vol. 1807 of Lecture Notes in Comput. Sci., Springer, Berlin, 2000, pp. 392–407. 4 [19] G. D’Alconzo, A. Gangemi, L. Romano, and G. Romeo, Rethinking r-PKP: a New Formulation for the Relaxed Permuted Kernel Problem. Cryptology ePrint Archive, Paper 2026/631, 2026. 1 [20] L. De Feo, D. Kohel, A. Leroux, C. Petit, and B. Wesolowski, SQISign: compact post-quantum signatures from quaternions and isogenies, in Advances in cryptology—ASIACRYPT 2020. Part I, vol. 12491 of Lecture Notes in Comput. Sci., Springer, Cham, [2020] ©2020, pp. 64–93. 1 [21] C. Delfs and S. D. Galbraith, Computing isogenies between supersingular elliptic curves over Fp , Des. Codes Cryptogr., 78 (2016), pp. 425–440. 1 [22] V. Dubois and N. Gama, The Degree of Regularity of HFE Systems, in Advances in cryptology—ASIACRYPT 2010, vol. 6477 of Lecture Notes in Comput. Sci., Springer, Berlin, 2010, pp. 557–576. 5 [23] J.-C. Faugére, A new efficient algorithm for computing Gröbner bases (F4 ), vol. 139, 1999, pp. 61–88. Effective methods in algebraic geometry (Saint-Malo, 1998). 4, 19 [24] J.-C. Faugère, A new efficient algorithm for computing Gröbner bases without reduction to zero (F5 ), in Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ACM, New York, 2002, pp. 75–83. 4 [25] J. C. Faugère, P. Gianni, D. Lazard, and T. Mora, Efficient Computation of Zero-dimensional Gröbner Bases by Change of Ordering, J. Symbolic Comput., 16 (1993), pp. 329–344. 5 [26] S. D. Galbraith, C. Petit, and J. Silva, Identification Protocols and Signature Schemes Based on Supersingular Isogeny Problems, J. Cryptology, 33 (2020), pp. 130–175. 1 [27] J. Herzog and T. Hibi, Monomial Ideals, Springer, 2011. 17 [28] M.-D. A. Huang, M. Kosters, Y. Yang, and S. L. Yeo, On the last fall degree of zero-dimensional Weil descent systems, J. Symbolic Comput., 87 (2018), pp. 207–226. 5 [29] D. Husemöller, Elliptic Curves, vol. 111 of Graduate Texts in Mathematics, Springer-Verlag, New York, second ed., 2004. With appendices by Otto Forster, Ruth Lawrence and Stefan Theisen. 5 [30] B. W. Jordan, A. G. Keeton, B. Poonen, E. M. Rains, N. Shepherd-Barron, and J. T. Tate, Abelian varieties isogenous to a power of an elliptic curve, Compositio Mathematica, 154 (2018), p. 934–959. 6
24
ALESSIO CAMINATA, ANDREA SANGUINETI, AND SILVIA SCONZA
[31] D. R. Kohel, Endomorphism rings of elliptic curves over finite fields, PhD thesis, University of California, Berkeley, 1996. 7 [32] A. Meneghetti, A. Pellegrini, and M. Sala, On the equivalence of two post-quantum cryptographic families, Ann. Mat. Pura Appl. (4), 202 (2023), pp. 967–991. 1 [33] K. Okeya, H. Kurumatani, and K. Sakurai, Elliptic Curves with the Montgomery-Form and Their Cryptographic Applications, in Public key cryptography (Melbourne, 2000), vol. 1751 of Lecture Notes in Comput. Sci., Springer, Berlin, 2000, pp. 238–257. 7 [34] K. Pardue, Generic sequences of polynomials, J. Algebra, 324 (2010), pp. 579–590. 18 [35] J. Renes, Computing Isogenies Between Montgomery Curves Using the Action of (0, 0), in Post-quantum cryptography, vol. 10786 of Lecture Notes in Comput. Sci., Springer, Cham, 2018, pp. 229–247. 2, 3, 7, 8, 12, 13 [36] L. Robbiano and M. Kreuzer, Computational Commutative Algebra 1, Springer-Verlag, Berlin Heidelberg, 2000. 16 [37] , Computational Commutative Algebra 2, Springer-Verlag, Berlin Heidelberg, 2005. 16, 18 [38] M. A. Saeed, Algebraic Approach for Code Equivalence, PhD thesis, Normandie Université; University of Khartoum, 2017. 1 [39] F. Salizzoni, An upper bound for the solving degree in terms of the degree of regularity, Transactions on Mathematical Cryptology, 5 (2025), pp. 1–7. 2, 16 [40] R. Schoof, Nonsingular Plane Cubic Curves over Finite Fields, J. Combin. Theory Ser. A, 46 (1987), pp. 183– 211. 7 [41] J. H. Silverman, The Arithmetic of Elliptic Curves, vol. 106 of Graduate Texts in Mathematics, SpringerVerlag, New York, 1986. 6, 8 [42] M. J. Steiner, The Complexity of Algebraic Algorithms for LWE, in Advances in cryptology—EUROCRYPT 2024. Part III, vol. 14653 of Lecture Notes in Comput. Sci., Springer, Cham, [2024] ©2024, pp. 375–403. 1 [43] A. Sutherland, MIT Lecture Notes, 18.783 - Spring 2021, tech. rep., MIT, 2021. 5 [44] Y. Takahashi, M. Kudo, R. Fukasaku, Y. Ikematsu, M. Yasuda, and K. Yokoyama, Algebraic approaches for solving isogeny problems of prime power degrees, J. Math. Cryptol., 15 (2021), pp. 31–44. 1, 2, 3, 5, 16, 20 [45] J. Tate, Endomorphisms of abelian varieties over finite fields, Invent. Math., 2 (1966), pp. 134–144. 9 [46] The Sage Developers, SageMath, the Sage Mathematics Software System (Version x.y.z), 2025. https://www.sagemath.org. 6 [47] K. Tsukazaki, Explicit isogenies of elliptic curves, PhD thesis, University of Warwick, 2013. 6 [48] L. C. Washington, Elliptic Curves, Discrete Mathematics and its Applications (Boca Raton), Chapman & Hall/CRC, Boca Raton, FL, second ed., 2008. Number theory and cryptography. 1 Dipartimento di Matematica, Università di Genova, via Dodecaneso 35, 16146, Genova, Italy Email address: [email protected] Dipartimento di Matematica, Università di Genova, via Dodecaneso 35, 16146, Genova, Italy Email address: [email protected] Institute of Mathematics, University of Zurich, Zurich, Switzerland Email address: [email protected]