The Supersingular Isogeny Problem in Time and Memory p1/3+o(1), Unconditionally José Luis Delgado
arXiv:2609.22018v1 [cs.CR] 18 Sep 2026
Independent Researcher
Abstract. Given a supersingular elliptic curve E/Fp2 , the OneEnd problem asks for a non-scalar endomorphism of E. By known reductions, solving this problem also solves the supersingular endomorphism ring and isogeny problems. Wesołowski obtained exponent 1/3 under an assumption on the factorization of a small degree, whereas the previous unconditional exponent was 2/5. We give a Las Vegas algorithm, analyzed without a smoothness heuristic, with expected time and memory
p
p1/3 exp O(
log p log log p) = p1/3+o(1) .
The algorithm fixes in advance a family of degrees that are products of small primes. Known counting results provide many isogenies of these degrees from curves to their Frobenius conjugates, and a collision estimate shows that the isogenies occur on sufficiently many distinct curves for a random walk to reach one of them. From such a curve, the algorithm splits a degree into two parts, enumerates two lists of shorter isogenies, and matches their targets to obtain an isogeny to the conjugate, whose composition with Frobenius gives the required endomorphism.
1
Introduction
1.1
The problem
For a supersingular elliptic curve E/Fp2 , the OneEnd problem asks for a non-scalar endomorphism of E. Unconditional reductions connect it to the computation of the full ring End(E) and of an isogeny between two supersingular curves [PW24, HLMW25], so an improved algorithm for OneEnd yields improved algorithms for all three problems. These problems govern the security of several cryptographic constructions based on supersingular isogenies, and their generic classical cost was p1/2+o(1) for many years. Wesołowski reduced the exponent to 1/3 under a heuristic about smooth integers [Wes26], and Udovenko later obtained an unconditional exponent of 2/5 [Udo26]. The question left between these results is: Can the exponent 1/3 be reached without a smoothness assumption? The algorithm developed here attains this exponent unconditionally, using the same starting observation as both preceding algorithms. Write E (p) for the curve obtained by applying the p-power map to the coefficients of E. Given a separable isogeny φ : E −→ E (p) . The relative Frobenius πE (p) : E (p) → E then gives πE (p) ◦ φ ∈ End(E). E-mail: [email protected] (José Luis Delgado)
2
The supersingular isogeny problem
The resulting endomorphism has inseparable degree p, whereas an integer multiplication has inseparable degree with even p-adic valuation, so the displayed endomorphism is not scalar. The remaining task of finding φ begins with the theorem of Aubry, Oyono, and Vincent, which guarantees such an isogeny of degree at most (p/2)1/3 [AOV26], but their existence theorem specifies the size of the degree and leaves its factorization unspecified. A large prime factor makes a direct search too expensive, and Wesołowski handles this obstruction by assuming that the least possible degree behaves like a random integer and is smooth often enough. The argument below attains the same exponent through a family of degrees with prescribed factorizations.
1.2
The basic search
Consider first a degree d = ℓ1 ℓ2 , where ℓ1 and ℓ2 are distinct small primes, and suppose that an isogeny φ : E → E (p) of degree d factors through an intermediate curve C: λ
η
E− →C− → E (p) ,
deg λ = ℓ1 ,
deg η = ℓ2 .
With ρ = ηb : E (p) → C, a list of the degree ℓ1 isogenies from E and a list of the degree ℓ2 isogenies from E (p) both contain C, and matching those entries recovers φ = ρb ◦ λ. The same construction works when a suitable degree d factors as d = uv,
gcd(u, v) = 1,
with u and v of comparable size. For a cyclic isogeny φ : E → E (p) of degree d, splitting its prime factors between u and v produces a curve C and isogenies λ : E −→ C,
ρ : E (p) −→ C
of degrees u and v. They again recover the original map through φ = ρb ◦ λ. a direct algorithm: list the isogenies of degree at most about √ This factorization gives d from both E and E (p) , then match entries whose targets are isomorphic. Each match recovers φ, and the work is essentially the combined size of the two lists. The factorization of d determines the cost of this search: when d is a product of small primes, both lists can be constructed by following isogenies of those prime degrees; an unknown prime factor of size close to d requires a search beyond the target cost. Wesołowski applies this search to the least degree from E to E (p) , so its success depends on the factorization of one integer. Our construction first chooses a large family Dp in which every degree is squarefree and smooth, and then proves that many supersingular curves admit an isogeny to their conjugate whose degree belongs to this family.
1.3
Coverage by the chosen degrees
For one degree d, results of Chenu and Smith count many pairs consisting of a curve and a √ cyclic degree d isogeny to its conjugate [CS22]. The number of such pairs is of order pd, up to logarithmic factors. Summing this count over d ∈ Dp gives enough pairs for the algorithm, provided that they are distributed among sufficiently many curves. Concentration on a small set would reduce the probability that a random walk finds a
José Luis Delgado
3
useful curve, so the analysis must bound how often two degrees d and e occur on the same curve. For two isogenies φ, ψ : E −→ E (p) of squarefree degrees d and e, consider the composite γ=φ b ◦ ψ ∈ End(E) which has norm de. Distinct kernels give a non-scalar γ, whose trace t satisfies t2 < 4de. The element γ generates an imaginary quadratic field and determines the largest quadratic order in that field that embeds in End(E) through γ. The first isogeny becomes an invertible ideal of norm d in this order, and the existence of the second isogeny imposes an additional divisibility condition on that ideal. Once the ideal is fixed, the common endpoint of the two isogenies satisfies a square equation in the class group of the order; every nonempty fiber of this square map has the size of the 2-torsion subgroup, which genus theory bounds by a divisor function. Every pair of isogenies therefore yields arithmetic data of the stated form, and counting all compatible data gives an upper bound without requiring a converse √ construction. Summation over t and over the possible orders produces a bound of size de, apart from logarithmic and local factors, which prevents the isogenies counted by Chenu and Smith from concentrating on too few curves.
1.4
Main result
Theorem 1.1 (Main theorem). Let p > 3 be prime. There is a classical Las Vegas algorithm which, given a supersingular elliptic curve E/Fp2 , returns a non-scalar endomorphism α ∈ End(E) \ Z, in efficient representation, in expected time and memory p p1/3 exp O( log p log log p) = p1/3+o(1) . The returned endomorphism satisfies log deg α = O(log p), and the algorithm and its analysis are unconditional. Corollary 1.2. The supersingular endomorphism ring problem and the supersingular isogeny problem admit classical probabilistic algorithms with expected time and memory p1/3+o(1) . The proof rests on an estimate for the distribution of the chosen degrees among curves. In the terminology of Chenu and Smith, a (d, +1)-structure is a separable cyclic isogeny φ : E → E (p) of degree d such that φ b = φ(p) . For a generic model E, let rd (E) count the cyclic kernels that support such an isogeny. If d, e ≥ 2 are squarefree and prime to p, then X X Y √ 3 rd (E)re (E) − 1d=e rd (E) ≪ de log2 (2de) 1+ . ℓ E
E
ℓ|gcd(d,e)
The implied constant is absolute, the subtraction removes the repeated use of one kernel, and the product records the extra choices at primes shared by √ the two degrees. Apart from logarithms and the displayed product, the bound grows like de, which prevents the isogenies from concentrating on a few curves. Its proof assigns arithmetic data to each pair of isogenies and counts the resulting data; Theorem 3.5 gives the finite form of the estimate.
4
1.5
The supersingular isogeny problem
Algorithmic use of the collision bound
For n = ⌊log2 p⌋ + 1, Section 4 specifies the primes and the number of factors in a set Dp of squarefree degrees chosen before sampling. Every prime factor is small enough for direct enumeration, and every member satisfies p d ≤ p1/3 exp O( log p log log p) . The Chenu–Smith count gives the total number of isogenies for each d, Tatuzawa’s theorem supplies the required lower bound for every degree except possibly one, and the collision theorem controls how often two counted isogenies occur on the same curve. Together these estimates show that an inverse polynomial proportion of the generic supersingular models supports the required isogenies, with the numerical bound of Theorem 4.4. Using these estimates, each trial of the algorithm performs the following five steps. (1) Move from the input along a lazy walk in the 2-isogeny graph until, after O(log p) steps, the endpoint is close to the stationary distribution. (2) At the endpoint E, list the relevant isogenies from E and from E (p) , and split every candidate degree into two parts of comparable size. (3) Match records that reach isomorphic curves, using a coloring of the prime factors to enforce disjoint supports without testing every pair of records. (4) Compose the matched records to obtain φ : E → E (p) , and verify every map and isomorphism used in the construction. (5) Form ω b ◦ πE (p) ◦ φ ◦ ω, where ω is the initial walk, and convert the result to an efficient representation. A trial without a match is repeated, whereas every returned map has passed deterministic checks; randomness therefore affects the running time but not correctness.
1.6
Relation to previous algorithms
The outer construction follows Algorithms 2 and 3 of [Wes26], which walk to a new curve, search from the curve and its conjugate, compose the result with Frobenius, and return along the walk. Our algorithm retains these steps and replaces the heuristic source of a smooth degree with the family Dp and the collision bound. Algorithm 1 of [Udo26] uses the same walk, Frobenius, and return path, and detects one chosen degree through a modular polynomial and bivariate multipoint evaluation. Our argument uses the Chenu–Smith count in the form developed there. The theorem is asymptotic, with a large subexponential factor and memory of the same order as the running time; practical attack costs and concrete security levels lie outside its scope. The reduction to Isogeny permits an unrestricted output degree, while a prescribed prime degree lies outside the statement.
1.7
Organization
Section 2 fixes the computational model and notation; Section 3 proves the collision bound; Section 4 constructs Dp and proves that many curves support its degrees; and Section 5 derives the algorithm and its running time from that density statement.
José Luis Delgado
5
2
Preliminaries
2.1
Elliptic curves and isogenies
The counting argument takes place over Fp2 , with any other field displayed explicitly, and all endomorphism rings are geometric. The choice of input model in Section 5.1 is the sole use of an extension, whose degree is at most two. An isogeny φ : E → E ′ is a nonconstant rational homomorphism of groups, and its degree is the degree of the rational map. It is separable when deg φ = # ker φ, and cyclic when its geometric kernel is cyclic. Each isogeny has a unique dual φ b : E ′ → E satisfying φ b ◦ φ = [deg φ],
φ◦φ b = [deg φ].
Maps are composed from right to left, so ψ ◦ φ applies φ first. An elliptic curve in characteristic p is supersingular if it has no nonzero geometric p-torsion; it then has a model over Fp2 , and its endomorphism ring is a maximal order in the quaternion algebra over Q ramified at p and infinity. We write End0 (E) = End(E) ⊗Z Q. The map a 7→ [a] identifies Z with the center of End(E), whose elements are the scalar endomorphisms; an element of End(E) \ Z is non-scalar. On End(E), the degree is the reduced norm, and the reduced trace of u is u + u b.
2.2
Efficient representations and computational problems
Because the degree of an isogeny may be exponential in the input length, writing the whole rational map can require too much space, so we use the output convention of [Wes26, HLMW25]. Definition 2.1 (Efficient representation). An algorithm A that runs in polynomial time is an efficient isogeny evaluator if, for every D ∈ {0, 1}∗ such that A(validity, D) = ⊤, there is an isogeny φ : E → E ′ , defined over a finite field Fq , such that (1) A(curves, D) = (E, E ′ ); (2) A(degree, D) = deg φ; (3) for P ∈ E(Fqk ), A(eval, D, P ) = φ(P ). If, moreover, the length of D is polynomial in log deg φ + log q, then D is an efficient representation of φ with respect to A. During the search, a map is stored as a chain of isogenies of small degree and converted by isogeny interpolation into an efficient representation before it is returned, as proved in Section 5.7. As in [Wes26], all isogenies returned in the following computational problems are encoded in an efficient representation. Problem 2.2 (OneEnd). Given a supersingular elliptic curve E defined over Fp2 , find an endomorphism in End(E) \ Z. For a function λ, the bounded problem OneEndλ of [HLMW25] further requires log deg α ≤ λ(log p). Problem 2.3 (EndRing). Given a supersingular elliptic curve E defined over Fp2 , find four endomorphisms generating End(E) as a Z-module. Problem 2.4 (Isogeny). Given supersingular elliptic curves E and E ′ defined over Fp2 , compute an isogeny φ : E → E ′ .
6
The supersingular isogeny problem
Page–Wesołowski and Herlédan Le Merdy–Wesołowski give probabilistic reductions between these three problems [PW24, HLMW25]. The reductions run in polynomial time and are unconditional, so the new complexity bound may be proved for OneEnd and then transferred to the other two problems. Computational model. We use a word RAM model with word size Θ(log p), in which field operations in Fp2 and memory accesses have unit cost when only the exponent of p is at issue. We retain polynomial factors in log p and every subexponential factor that is displayed. Isogenies of small prime degree can be evaluated with Vélu formulas or modular polynomials, and every table constructed below has size within the stated complexity bound. Throughout the paper, log is the natural logarithm and log2 has base two.
2.3
Models, Frobenius, and isogenies to the conjugate
For a prime p > 3 and each supersingular invariant j, fix a model Ej /Fp2 on which the p2 -Frobenius is [−p]; this model is maximal over Fp2 , since #Ej (Fp2 ) = (p + 1)2 . If j ∈ / {0, 1728}, this condition selects one of the two quadratic twists over Fp2 ; such invariants are called generic. As in [Wes26, Udo26], E (p) denotes the curve obtained by applying the p-power map to every coefficient of E. Following Udovenko, write πE : E −→ E (p) ,
πE (p) : E (p) −→ E
for the two relative Frobenius maps. On the models just fixed, they satisfy πE (p) ◦ πE = [−p],
π[ E (p) = −πE .
(1)
Comparison of notation. The same maps have different names in the two references: our φ : E → E (p) is denoted by ϕ in [Wes26] and by ψ in [Udo26], while our π is denoted by φ in [Wes26] and by π in [Udo26]. We use ω for the initial walk, as in [Wes26]; in particular, πE (p) ◦ φ is the map written φ ◦ ϕ in [Wes26] and π ◦ ψ in [Udo26]. For an endomorphism u, write Trd(u) = u + u b ∈ Z,
Nrd(u) = deg u.
The degree is a positive definite quadratic form with polar form B(u, v) = Trd(b u ◦ v), and hence p | Trd(b u ◦ v)| ≤ 2 deg u deg v. (2) Definition 2.5 (Chenu–Smith structure). Let d be prime to p and let ε ∈ {±1}. A pair (E, φ), where φ : E → E (p) is a separable cyclic isogeny of degree d, is a (d, ε)-structure if φ b = εφ(p) .
(3)
All subsequent counts use ε = +1; on a generic maximal model, the maps φ and −φ have the same kernel, which the counts include once. Let rd (E) be the number of cyclic kernels supporting a (d, +1)-structure on E. For squarefree d, e coprime to p, define the ordered collision count X X + Cd,e (p) = rd (E)re (E) − 1d=e rd (E). (4) E
E
The sum runs over the generic maximal models fixed above. When d = e, the subtracted term removes the pair formed from one kernel twice, while two distinct kernels of the same degree still contribute.
José Luis Delgado
2.4
7
Signs of small conjugate isogenies
The sign used in the counts is forced for every sufficiently small isogeny to the conjugate. Indeed, the completion of End(E) at p is the maximal order in the quaternion division algebra over Qp , and every inseparable endomorphism belongs to its maximal two-sided ideal. Its reduced trace therefore lies in pZp ; see [Voi21, Chapter 13]. Lemma 2.6. If u ∈ End(E) is inseparable, then p | Trd(u). Proposition 2.7 (Sign of small conjugate isogenies). Let φ : E → E (p) be separable and cyclic of degree d. If 4d < p, then (E, φ) is a (d, +1)-structure; equivalently, φ b = φ(p) . Proof. The map α = πE (p) ◦ φ is inseparable of degree pd, so Lemma 2.6 gives p | Trd(α), while Inequality (2) gives p | Trd(α)| ≤ 2 pd < p. The only multiple of p in this interval is zero, so Trd(α) = 0 and α b = −α. Equation (1) and the naturality of Frobenius now give φ b ◦ πE = φ(p) ◦ πE ; the common right factor πE is surjective, so φ b = φ(p) .
2.5
Orientations and ideal isogenies
The collision proof uses the following part of the correspondence between isogenies and ideals. Let K be an imaginary quadratic field, and let O ⊂ K be an order. An O-orientation of E is an embedding ι : O ,→ End(E). The orientation is primitive, also called optimal, if ι(K) ∩ End(E) = ι(O). An isomorphism from (E, ι) to (E ′ , ι′ ) is an isomorphism f : E → E ′ such that f ◦ ι(a) = ι′ (a) ◦ f for every a ∈ O. If a is an invertible integral O-ideal prime to p, its kernel subgroup is E[a] = {P : ι(a)P = 0 for every a ∈ a}. The quotient by this subgroup has degree N (a), and its target inherits an O-orientation. Because principal ideals preserve the oriented isomorphism class, this construction defines an action of Pic(O). Onuki’s reduction theorem shows that the primitive orientations needed below form at most two free torsors under this group [Onu21], as used in Section 3.2. An oriented isogeny is horizontal if its source and target have the same order. A horizontal cyclic isogeny whose degree is prime to the conductor is represented by an invertible ideal. Below, this correspondence is applied in the forward direction to isogenies that already exist.
2.6
The quadratic order attached to a pair
Each pair counted by (4) determines a quadratic order as follows. Let φ, ψ : E → E (p) define (d, +1)- and (e, +1)-structures, where d and e are squarefree. Put γ=φ b ◦ ψ,
t = Trd(γ),
∆ = 4de − t2 .
(5)
Since the reduced norm of γ is de, γ 2 − tγ + de = 0.
(6)
Lemma 2.8. The subtracted pair in (4) is precisely the case in which γ is scalar. Every nonsubtracted pair has ∆ > 0.
8
The supersingular isogeny problem
Proof. If γ = [a], then a2 = de, and the squarefreeness of d and e implies d = e and a = ±d. The identity φ ◦ γ = [d] ◦ ψ then gives ψ = ±φ, so the kernels coincide; conversely, equal kernels give this scalar case. For non-scalar γ, the strict form of (2) gives t2 < 4de. For a nonsubtracted pair, let K = Q(θ),
θ2 − tθ + de = 0,
ι(θ) = γ,
and define the order selected by this embedding: O = ι−1 End(E) ∩ ι(K) .
(7)
This order is primitive by definition, and if h = [O : Z[θ]] and D = disc(O) < 0, then −∆ = h2 D.
(8)
The criterion for the existence of a primitive orientation implies that p does not split in K and that p ∤ cond(O) [Onu21, Proposition 3.2]. Let c be the nontrivial automorphism of K/Q. The two identities with sign +1 give φ ◦ γ = [d] ◦ ψ = γ b(p) ◦ φ.
(9)
Thus φ is an oriented isogeny from x = (E, ι) to Jx = (E (p) , ι(p) ◦ c).
(10)
Lemma 2.9 (Order preservation for squarefree degrees). The oriented isogeny φ : x → Jx is horizontal, is represented by an invertible integral O-ideal a of norm d, and satisfies gcd(de, cond(O)) = 1.
(11)
Proof. Factor φ into steps of prime degree, and transport the orientation through the factorization. A step of degree ℓ can change the order only at ℓ, because after ℓ is inverted, conjugation by that step identifies the two endomorphism rings. Since d is squarefree, there is at most one step of degree ℓ, while every other step preserves the localization at ℓ. The orders at the start and at the end are both O, so the step of degree ℓ must preserve that localization as well. Applying this argument to each ℓ | d shows that every step is horizontal, and φ is represented by an invertible ideal of norm d [Onu21, Section 3]. Applying the same argument after exchanging φ and ψ proves (11).
3
The collision theorem
A pair (φ, ψ) as in Section 2 determines the order O, the element θ, and an ideal a of norm d. The existence of ψ restricts the possible ideals a, and the endpoint condition becomes a square equation in Pic(O), whose fibers are bounded by genus theory. An elementary divisor estimate then sums these bounds over the trace and the order, yielding an upper bound for the number of curves on which two degrees occur.
3.1
The compatibility condition
Let a be the invertible O-ideal of norm d associated with φ by Lemma 2.9. The relation aa = dO identifies the subgroup E[a] ⊂ E[d] with a/dO, after a choice of module coordinates. Lemma 3.1 (Restriction from the second isogeny). For every collision pair, (θ) ⊆ a.
(12)
José Luis Delgado
9
Proof. For ℓ | d, Equation (11) shows that O ⊗ Zℓ is the maximal order of K ⊗ Qℓ . The Tate module Tℓ (E) is free of rank one over this order; when the local algebra is a field, its order is a discrete valuation ring, and when it is split, its two idempotents give two summands of rank one over Zℓ . After choosing an identification, we have E[d] ≃ O/dO as O-modules, and E[a] corresponds to a/dO. The identity (9) reads φ ◦ ι(θ) = [d] ◦ ψ, whose right side kills E[d]; hence ι(θ)E[d] ⊆ ker φ = E[a]. In the chosen coordinates, this inclusion becomes θ(O/dO) ⊆ a/dO. Because dO = aa is contained in a, the last inclusion is equivalent to θO ⊆ a, which is the required ideal condition. The ideals allowed by this condition can be counted in the coordinates √ δ+ D t − hδ δ ≡ D (mod 2), ω= , θ = a0 + hω, a0 = . 2 2
(13)
The traces of θ and hω have the same parity, so a0 ∈ Z. Lemma 3.2 (Compatible ideals of prescribed norm). For a fixed triple (t, O, h) satisfying (8), the number of invertible integral ideals a of norm d satisfying (12) is Y D ID,h (d, e, t) = 1+ , (14) ℓ ℓ|gcd(d,h)
where the symbol at 2 is the Kronecker symbol. In particular, ID,h (d, e, t) ≤ 2ω(gcd(d,e,t)) .
(15)
Proof. Because the integer d is squarefree and prime to the conductor, the ideal can be chosen separately at each ℓ | d. Ideals of norm ℓ correspond to roots modulo ℓ of the monic polynomial of ω, and the condition θ ∈ a imposes one linear congruence on that root. If ℓ ∤ h, the congruence selects the residue −a0 /h. Since N (θ) = de ≡ 0 (mod ℓ), this residue is a root of the polynomial of ω and gives one local ideal. If ℓ | h, the norm identity gives ℓ | a0 , so the linear condition imposes no restriction and the number of roots is 1 + (D/ℓ): two if ℓ splits, one if it ramifies, and zero if it is inert. The same statement holds at 2 with the Kronecker symbol, and multiplication of the local counts proves (14). A local factor equals two only when ℓ | d, h and ℓ splits in O. The relation h2 D = t2 −4de, together with squarefreeness, then implies ℓ | e, t. For odd ℓ, this follows by reducing the relation modulo ℓ2 ; for ℓ = 2, it follows from D ≡ 1 (mod 8) and the norm formula in (13). Hence every prime that contributes a factor two divides gcd(d, e, t), proving (15).
3.2
The square equation in the class group
For G = Pic(O), Onuki proves that the action on the reduction orbit of a primitive O-oriented curve is free and transitive. Every primitive orientation needed here belongs either to that orbit or to its Frobenius image [Onu21, Proposition 3.3 and Theorem 3.4], so at most two G-torsors occur. Conjugation inverts an ideal class, whereas Frobenius commutes with the ideal action; hence the operation J from (10) satisfies J(b ∗ x) = b−1 ∗ Jx.
(16)
10
The supersingular isogeny problem
Consider one of the torsors on which the endpoint condition has a solution. Choose x0 in that torsor with Jx0 = c0 ∗ x0 , and write every other point as x = b ∗ x0 . The isogeny represented by a ends at Jx precisely when a ∗ x = Jx, or equivalently b2 = [a]−1 c0 .
(17)
Thus the endpoint condition is a square equation in G, and each nonempty fiber of the square map has cardinality |G[2]|. The two possible torsors therefore contribute at most 2|G[2]| oriented curves for each allowed ideal. + The passage from oriented maps to the kernels counted by Cd,e (p) requires accounting for signs. Each kernel determines its isogeny up to sign, and among the four choices (±φ, ±ψ), changing both signs leaves γ unchanged, whereas changing one sign replaces γ by −γ. A pair of kernels therefore gives two oriented data: γ=φ b◦ψ
and
− γ.
These data are distinct even when t = 0, because the automorphisms of a generic curve are the central elements ±1, whose conjugation fixes every endomorphism; a non-scalar endomorphism and its negative therefore define distinct data. Conversely, the oriented datum fixes γ, and a fixes the kernel of φ. For data obtained from an actual pair, the identity φ◦γ ψ= (18) d is integral and fixes the kernel of ψ. Changing both signs changes neither kernel, so the two data obtained from each pair cancel the factor two from the two torsors and give X X + Cd,e (p) ≤ ID,h (d, e, t) | Pic(O)[2]|. (19) t2 <4de O⊇Z[θ]
Equation (19) injects the geometric pairs into the arithmetic data on the right, so counting all such data gives a valid upper bound even when some terms are not realized by isogenies.
3.3
Sum over quadratic orders
The sum over O is controlled by a bound for the 2-torsion in its class group. The following constant applies to nonmaximal orders and also covers the prime 2. Lemma 3.3 (Quadratic 2-torsion). If O is an imaginary quadratic order of discriminant D < 0, then | Pic(O)[2]| ≤ 13 2ω(|D|) . (20) Proof. An element of order at most two is represented by a primitive, reduced, ambiguous binary quadratic form. Such a form satisfies one of b = 0, |b| = a, or a = c. In these three cases the discriminant factors as |D| = 4ac,
|D| = a(4c − a),
|D| = (2a − b)(2a + b).
Primitivity makes the two factors coprime outside 2. Each odd prime power must therefore occur wholly in one factor. When b = 0, the power of 2 has at most two allocations, and each of the other two cases has at most four. Once the prime powers have been assigned, the reduction inequalities leave at most one form for each remaining choice. The total is at most (2 + 4 + 4)2ω(|D|) , which is bounded by the right side of (20), as in the usual proof through ambiguous forms [Cox13, Chapter 3].
José Luis Delgado
11
The orders containing Z[θ] have discriminants −∆/h2 , and the identity X 2 2ω(n/h ) = τ (n)
(21)
h2 |n
holds because both sides are multiplicative and equal a + 1 when n = ℓa . Applying it to (19), together with Lemmas 3.2 and 3.3, gives X + Cd,e (p) ≤ 13 2ω(gcd(d,e,t)) τ (4de − t2 ). (22) t2 <4de
3.4
An average divisor bound
The remaining sum involves only elementary arithmetic. For m ≥ 1, put S(m) =
X
τ (4m − t2 ),
P(X) =
t2 <4m
Y ℓ+1 . ℓ−1
ℓ≤X ℓ prime
√ Lemma 3.4. For every real Z ≥ 2 m, S(m) ≤ 6ZP(Z).
(23)
Proof. Let ρA (a) = #{u mod a : u2 ≡ A (mod a)}. Applying τ (n) ≤ 2 a≤√n, a|n 1 and summing first over the possible divisors a, the number of representatives of each residue class in |t| < Z gives X ρ4m (a) S(m) ≤ 6Z . (24) a P
a≤Z
For every prime ℓ and integer A, X ρA (ℓj ) j≥1
ℓj
≤
2 . ℓ−1
(25)
For the local bound, write v = vℓ (A). At level j ≤ v, the zero congruence gives ℓ⌊j/2⌋ roots. An odd v gives no roots above level v; if v = 2a, division by ℓ2a leaves a congruence asking for the square root of a unit, each root of which has ℓa lifts. For odd ℓ, a unit has at most two square roots at each level, and the two geometric sums are bounded by 2/(ℓ − 1). For ℓ = 2, a unit has at most 1, 2, 4 roots modulo 2, 4, 2j ; the part arising from zero is 2(1 − 2−a ), and the remaining tail is at most 21−a , with total at most 2, proving (25). The multiplicativity of ρA gives X ρ4m (a) Y 2 ≤ 1+ = P(Z). a ℓ−1 a≤Z
ℓ≤Z
Substituting this estimate in (24) proves the lemma. Theorem 3.5 (Finite collision bound). Let p > 3 and let d, e ≥ 2 be squarefree and coprime to p. Set l√ m X=2 de . Then + Cd,e (p) ≤ 78XP(X)
Y ℓ|gcd(d,e)
3 1+ . ℓ
(26)
12
The supersingular isogeny problem
In particular, + Cd,e (p) ≪
√
Y
2
de log (2de)
ℓ|gcd(d,e)
3 1+ ℓ
,
(27)
with an absolute implied constant, uniformly in p, d, e. Proof. Set m = de and g = gcd(d, e); since g is squarefree, X 2ω(gcd(g,t)) = 1. r|g r|t
For each such r, the relations r2 | m, t = ru, and τ (r2 n) ≤ 3ω(r) τ (n) show that the right side of (22) is then at most X 13 3ω(r) S(m/r2 ). r|g
Lemma 3.4, with Z = X/r, and the inequality P(X/r) ≤ P(X) give X 3ω(r) Y 3 78XP(X) = 78XP(X) 1+ , r ℓ r|g
ℓ|g
which is (26). Since (ℓ + 1)/(ℓ − 1) = (1 − ℓ−2 )(1 − ℓ−1 )−2 , the Mertens product estimate of Rosser and Schoenfeld [RS62] gives P(X) = O(log2 X), with the uniform bound P(X) ≤ 240 (1 + log X)2
(X ≥ 2).
(28)
√
Since X ≤ 3 de, this estimate also proves (27). Corollary 3.6 (Uniform form for a bounded family). Let n = ⌊log2 p⌋ + 1. If d, e ≤ B, 4B < p, and the hypotheses of Theorem 3.5 hold, then Y √ 3 + 50 2 Cd,e (p) ≤ 2 n de 1+ . (29) ℓ ℓ|gcd(d,e)
Proof. √Here X ≤ 2B < p/2, so 1 + log X ≤ n. Combining (26) with (28), and then using X ≤ 3 de and 234 · 240 < 250 , proves the claim.
4
Many curves with smooth isogenies to their conjugates
The degree family used by the algorithm is fixed deterministically before the sampling in Section 5. The Chenu–Smith count gives the total number of associated isogenies, and the collision theorem shows that these isogenies occur on many curves. Denote the bit length of p by n = ⌊log2 p⌋ + 1.
4.1
Isogeny count for one degree
Proposition 4.1 (Count for one degree). For every squarefree d ≥ 2 prime to p, X 1 Md := rd (E) ≥ hKd − 5Ψ(d), (30) 2 E √ where Kd = Q( −pd),QDKd is its fundamental discriminant, hKd = h(DKd ) is its class number, and Ψ(d) = d ℓ|d (1 + 1/ℓ).
José Luis Delgado
13
Here Ψ denotes the Dedekind psi function, as in [Udo26]; Wesołowski uses the distinct notation Ψ(X, B) for the number of smooth integers in an interval [Wes26]. Proof. In the notation of [Udo26, Theorem 3], Chenu and Smith count the isomorphism classes of (d, +1)-structures by 2hKd , −dp ≡ 1 (mod 8), αd = 4hKd , −dp ≡ 5 (mod 8), hKd , otherwise. The count agrees with [CS22, Corollary 4.15] for sign +1, and in every case αd ≥ hKd . Since the Frobenius trace of a (d, ε)-structure is −2εp, our choice of maximal model selects ε = +1 and fixes the twist. To pass from signed maps to the kernels counted by rd (E), observe that there are Y Ψ(d) = (ℓ + 1) ℓ|d
cyclic subgroups of order d in E[d]. After a kernel is fixed, the quotient map and an identification of its target with E (p) are determined up to an automorphism of E (p) . The automorphism groups at j = 0 and j = 1728 have orders 6 and 4, so the structures above these two invariants contribute at most 10Ψ(d) terms. On every generic maximal model, the automorphism group is {±1}, and the maps φ and −φ give one kernel. Removing the two special invariants and dividing by two yields Md ≥
1 αd − 10Ψ(d) ≥ hKd − 5Ψ(d), 2 2
which proves (30). 1+o(1)
, whereas the class number term has order √ For the degrees used below, Ψ(d) = d pd/ log p; every estimate retains the lower-order subtraction. Proposition 4.2 (Class number bound for the family). Let p ≥ 217 be prime, and let D be any family of squarefree degrees d ≥ 2 satisfying p ∤ d and 4d < p. Apart from at most one degree d∗ ∈ D, every d ∈ D satisfies √ pd − 5Ψ(d). (31) Md ≥ 80n Proof. Apply Tatuzawa’s theorem [Tat51] with ε = 1/ log p for every degree in D. The fundamental discriminant satisfies pd ≤ |DKd | ≤ 4pd < p2 . For p ≥ 217 , this discriminant also satisfies |DKd | ≥ max(e1/ε , e11.2 ). Tatuzawa’s theorem therefore gives, with at most one primitive real character excluded, L(1, χDKd ) > 0.655 ε|DKd |−ε . The class number formula for imaginary quadratic fields and the inequality |DKd |−1/ log p > e−2 imply √ 1 0.655 p pd hKd > pd > . 2 2 2πe log p 80n For the last inequality, use log p < n log 2 and 2πe2 log 2 < 80 · 0.655. Distinct squarefree degrees prime to p give distinct quadratic fields, so the exceptional character can affect at most one degree in D. Substitution of the class number bound in (30) proves the proposition.
14
The supersingular isogeny problem
4.2
Distinct curves
The preceding sum counts pairs (E, d), whereas the density estimate requires the number of distinct curves that occur among them. The following lemma combines the total count with the collision bounds: its first inequality counts points in the support, and its second counts points with two distinct labels. Lemma 4.3. Let X be finite, |X | ≤ N , and let ri : X → Z≥0 . Put R(x) =
X
ri (x),
S=
X
R(x),
x
i
and Cij =
X
ri (x)rj (x) − 1i=j
x
X
ri (x).
x
Suppose S ≥ S0 ≥ 0 and Cij ≤ Uij , where U is symmetric and nonnegative. If K = P U , i,j ij then S02 #{x : R(x) > 0} ≥ . (32) S0 + K Moreover, let (
V (x) =
X
1X V0 = max 0, S0 − Uii 2 i
1ri (x)>0 ,
i
) ,
K̸= =
X
Uij .
i̸=j
If V0 > N , then #{x : V (x) ≥ 2} ≥
(V0 − N )2 . V0 + K̸=
(33)
Proof. By the definition of Cij , X
R(x)2 = S +
x
X
Cij ≤ S + K.
i,j
Cauchy–Schwarz on the support of R, together with the monotonicity of s2 /(s + K), gives the first bound. P For every integer r ≥ 0, 1r>0 ≥ r − r(r − 1)/2, and hence x V (x) ≥ V0 . Moreover, X x
V (x)2 ≤
X
V (x) + K̸= .
x
P The points with V (x) ≤ 1 contribute at most N to x V (x); applying Cauchy–Schwarz to the remaining points and using the same monotonicity argument gives (33). The argument is deterministic and is based on the displayed count and collision bounds.
4.3
The degree family
The degrees searched by the algorithm contain the same number of prime factors, all drawn from a short interval. The interval is chosen so that the degrees are large enough to reach many curves and their factors remain small enough for enumeration. For n ≥ 216 let lnm h = ⌈log2 n⌉ , s = min{a ∈ 2Z : a2 ≥ nh}, k= + 4. (34) 3s
José Luis Delgado
15
Let q1 < · · · < qm be all primes in 2s < q ≤ 2s+4 , and define
(35)
( Dp =
) Y
qi : I ⊆ {1, . . . , m}, |I| = k
.
(36)
i∈I
Every member of Dp is squarefree, and all its prime factors are at most 2s+4 . The elementary prime estimates of Rosser and Schoenfeld [RS62] imply 4 · 2s (37) s in our range. This weak bound can also be recovered directly from central binomial coefficients and Chebyshev’s function. For each qi , set 2 3vi √ √ v i = ⌈ qi ⌉ , bi = vi2 + wi = ⌊ qi ⌋ , . qi m≥
Let ek denote the elementary symmetric polynomial of degree k, and put A = ek (w1 , . . . , wm ),
W =
m Y
wi ,
(38)
J = ek (q1 + 3, . . . , qm + 3),
(39)
i=m−k+1
Z = ek (q1 + 1, . . . , qm + 1), m Y H = [X k Y k ] (1 + vi X + vi Y + bi XY ),
Hdiag = ek (b1 , . . . , bm ).
(40)
i=1
These five quantities collect the terms in the lower bound and in the collision bounds: Quantity A W Z J H
Use in the calculation √ P lower bound for d∈Dp d largest term that may be lost to Tatuzawa’s exception sum of the penalties involving the Dedekind psi function upper bound for collisions that use the same degree upper bound for all ordered pairs of colliding degrees
Expanding the four terms in each factor of the definition of H gives X √ Y 3 de 1+ H≥ , ℓ d,e∈Dp
(41)
ℓ|gcd(d,e)
and H − Hdiag is an upper bound for the same sum over d ̸= e. An index used only by d √ or only by e contributes vi ≥ qi , whereas an index common to both contributes 3 bi ≥ qi + 3 = qi 1 + . qi Q Q For equal degrees, the required upper bound is J, since d ℓ|d (1 + 3/ℓ) = ℓ|d (ℓ + 3). The parameters satisfy the following bounds, whose derivation also gives a uniform choice of the constants hidden in the o(1) term: p p s = O( n log n), k = O( n/ log n), (42) B := max d ≤ 2n/3+6s < 2n/2 , d∈Dp
A ≥ 2n/2+5s , H ≤ 8A2 ,
4B < p,
(43)
W ≤ A/4, √ Z, J ≤ 2 B A.
(44) (45)
16
The supersingular isogeny problem
√ √ The inequalities nh ≤ s < nh + 2 and n ≥ 2048h hold in the stated range. Hence s ≥ 32h, 40s ≤ n, and k ≤ n/(3s) + 5. These inequalities give k(s + 4) ≤ n/3 + 6s and (43). From (37), m/k ≥ 2s−h , while wi ≥ 2s/2 ; therefore m ks/2 A≥ 2 ≥ 2k(3s/2−h) ≥ 2n/2+5s . k The upper bound W ≤ 2k(s/2+2) . implies A/W ≥ 2k(s−h−2) ≥ 4, which proves W ≤ A/4. Finally, vi ≤ 1 + 2−s/2 , wi
bi ≤ 1 + 4 · 2−s . vi2
Comparing a term of H with the corresponding ordered pair of terms in A2 introduces at most 2k factors of the first type and k factors of the second type. Since k ≤ n ≤ 2h ≤ 2s/32 , the logarithm of their product is at most 2k 2−s/2 + 4k 2−s < log 8. Consequently H ≤ 8A2 . Similarly, for c ∈ {1, 3} and any k-set I, sY Y Y √ Y (qi + c) ≤ 2 qi wi ≤ 2 B wi . i∈I
i∈I
i∈I
i∈I
The factor 2 in this inequality follows from the bound qi + c 1 + 3/qi ≤ √ −1/2 qi wi 1−q i
and k 3 · 2−s +
2−s/2 1 − 2−s/2
< log 2,
h where the √last inequality follows from s ≥ 32h and k ≤ 2 . Summing over all sets I proves Z, J ≤ 2 B A, and hence (45).
Theorem 4.4 (Density of smooth isogenies to conjugates). Let p > 3 be prime of bit length n ≥ 216 . For the deterministic family Dp in (36), at least p 280 n4
(46)
generic supersingular maximal models admit (d, +1)-structures for at least two distinct degrees d ∈ Dp . Every such degree satisfies p d ≤ p1/3 exp O( log p log log p) , (47) √ and all its prime factors are exp(O( log p log log p)). √ Proof. Remove the possible exceptional degree from Proposition 4.2, and put ρ = p . The sum of the remaining first moments is at least ρ(A − W ) S0 = max 0, − 5Z . (48) 80n
José Luis Delgado
17
To justify the numerator,√recall that the primes are ordered increasingly. The degree with the largest value of d also has the largest product of the wi . Removing any one class number term therefore subtracts at most W from the lower bound A. We retain the penalty involving Ψ for the removed degree, thereby obtaining a weaker valid bound. Let Γ = 250 n2 . Corollary 3.6 and (41) bound all collisions by ΓH, with contributions at most ΓJ from equal degrees and at most Γ(H − Hdiag ) from distinct degrees. Lemma 4.3 therefore applies with V0 = max{0, S0 − ΓJ/2}. (49) The comparison between the main term and the error terms begins with Equation (43), which gives p p/B ≥ 2n/4−1/2 ≥ 262 n3 . Combining this inequality with (44)–(45) yields √ pA V0 ≥ ≥ 2p. 2048n There are fewer than p generic supersingular invariants, and moreover V0 ≤ S0 ≤ with V0 + Γ(H − Hdiag ) ≤ 16ΓA2 .
(50) √
pA ≤ A2
Applying (33) and using V0 − p ≥ V0 /2 gives #{E : at least two degrees} ≥
V02 p p ≥ 78 4 ≥ 80 4 . 2 64ΓA 2 n 2 n
Equations (42), (43), and (35) give (47) and the stated bound for the prime factors. Because the degree family is fixed before the algorithm samples any curve, the theorem establishes the factorization property required by the search from the count and collision estimate above.
5
Proof of the main result
The density theorem identifies a set of curves that support the required isogenies. The algorithm samples a nearly uniform curve, lists short isogenies from that curve and its conjugate, matches the two lists, and transports the resulting endomorphism back to the input.
5.1
Input model
The density theorem is stated on maximal models, whereas OneEnd permits an arbitrary supersingular input Ein /Fp2 ; the following reduction passes between these two descriptions. When j(Ein ) ∈ {0, 1728}, an automorphism of order 3 or 4 already gives a nonscalar endomorphism; on suitable Weierstrass models, one may use (x, y) 7→ (ζ3 x, y) or √ (x, y) 7→ (−x, −1 y). The required roots of unity lie in Fp2 , so the rest of the construction concerns a generic input. Let E⋆ be the fixed maximal model with j(E⋆ ) = j(Ein ). Because the two curves are quadratic twists, an isomorphism over the algebraic closure ν : Ein −→ E⋆
(51)
is defined over an extension of Fp2 of degree at most two. For the computation of the model and the isomorphism, set c = j(Ein )/(1728 − j(Ein )) and start from y 2 = x3 + 3cx + 2c,
18
The supersingular isogeny problem
whose invariant is j(Ein ). Point counting in time polynomial in log p distinguishes this curve from its quadratic twist: we select the one with (p + 1)2 rational points. Standard arithmetic in finite fields then recovers ν, with randomized polynomial time when roots are found by random sampling. Conjugation transfers an answer on E⋆ to the original curve: if α⋆ ∈ End(E⋆ ), then ν −1 ◦ α⋆ ◦ ν ∈ End(Ein ). This conjugate descends to Fp2 , since the Galois cocycle of the quadratic twist takes values in the central subgroup {±1} and fixes every conjugated endomorphism. Conjugation also preserves non-scalarity, and the bounded degrees of ν and ν −1 preserve efficient representability, so the search may start at E⋆ .
5.2
Sampling distribution
The supersingular 2-isogeny graph, with its natural automorphism weights, has stationary distribution 24 . (52) π(E) = (p − 1)# Aut(E) A generic vertex therefore has mass 12/(p − 1), while√the Ramanujan bound gives nontrivial normalized eigenvalues of absolute value at most 2 2/3. After making the walk lazy, the corresponding bound is smaller than 35/36; see [PW24]. Let µt be the distribution after t lazy steps from E⋆ , where at each step the walk stays put with probability 1/2 and otherwise chooses one of the three outgoing 2-isogenies uniformly. Since πmin > 1/p, √ t p 35 . (53) ∥µt − π∥TV ≤ 2 36 The choice
T =
(n/2 + 81) log 2 + 4 log n . log(36/35)
(54)
makes the bound in (53) at most 2−82 n−4 . Theorem 4.4 and (52) therefore imply Pr[∃d ∈ Dp : rd (E) > 0] ≥ 2−80 n−4 .
(55)
The stationary mass of the set counted by Theorem 4.4 is at least 12p/((p − 1)280 n4 ), whereas the mixing error is smaller than 2−82 n−4 . Consequently, the expected number of trials is O(n4 ), and computing and storing each walk costs a polynomial in n.
5.3
Factor splitting
Once the walk reaches a curve counted by Theorem 4.4, an isogeny from that curve to its conjugate has degree in Dp . The search splits its prime factors into two products of similar size, with parameters lp m Q = 2s+4 , B = max d, L= QB . d∈Dp
Lemma 5.1 (Factor splitting). Every d ∈ Dp has a factorization d = uv such that gcd(u, v) = 1,
u, v ≤ L,
and both u and v are squarefree products of primes from the interval (35). Proof. Process the prime factors of d in any order, multiplying at each step the smaller of two products by the next factor. The ratio of the larger product to the smaller one is then at most the largest factor processed so far and hence at most Q, which at the end gives max(u, v)2 ≤ Qd ≤ QB. Assigning each prime to only one product also gives gcd(u, v) = 1.
José Luis Delgado
19
The lemma reduces the search to two lists, obtained by enumerating from E and E (p) all cyclic isogenies of degree at most L whose degrees are squarefree products of primes from (35). Because the Frobenius of degree p2 is the scalar −p, every subgroup of order prime to p is stable under Galois; the quotient maps are therefore defined over Fp2 , and their targets are maximal. For every target C, store a key κ(C) that identifies its isomorphism class over Fp2 , consisting of its j-invariant and its quadratic, quartic, or sextic twist class, as appropriate. Each record also stores the set of prime factors and the chain of quotient maps, and the number of records in either list is at most X Ψ(a) = O(L2 ). (56) a≤L
The bound follows from Ψ(a) = a r|a µ2 (r)/r by summing first over r; restricting the allowed factors can only reduce the number of records. Standard routines based on Vélu formulas or modular polynomials enumerate each extension of prime degree in time polynomial in Q and n, while standard isomorphism tests over finite fields recover an isomorphism between curves with equal keys in probabilistic polynomial time. In particular, the key κ distinguishes the nonisomorphic twists over Fp2 that share the same j-invariant. P
Algorithm 1 Isogenies from one curve: ListIsogenies(E, L, Q) Require: A supersingular curve E, a bound L, and the ordered prime set Q = {q1 , . . . , qm } Ensure: One record for every cyclic squarefree isogeny supported on Q and of degree at most L 1: L ← ∅ 2: for all squarefree a ≤ L with Supp(a) ⊆ Q do 3: for all cyclic subgroups G ⊂ E[a] of order a do 4: construct the quotient chain λ : E → E/G, processing Supp(a) in increasing order 5: append (κ(E/G), E/G, | Supp(a)|, Supp(a), λ) to L 6: return L Processing the primes in a fixed order prevents several permutations of one chain from representing the same cyclic kernel. The procedure is an abstract description of the usual enumeration by a tree of isogenies. The complexity analysis counts every record and allows a polynomial amount of work in Q and n for every edge of prime degree. A meeting of records λ : E −→ C,
ρ : E (p) −→ C
gives φ = ρb ◦ λ : E −→ E (p) .
(57)
If the two supports are disjoint and have total cardinality k, then deg φ ∈ Dp and its kernel is cyclic. An isomorphism is inserted when the records use different models of the same endpoint.
5.4
List matching
A target curve can occur many times in both lists, and testing every pair of records with that target would exceed the claimed complexity. Color coding [AYZ95] selects compatible records without forming this Cartesian product.
20
The supersingular isogeny problem
Independently color each prime in (35) left or right. Retain on the E side only records all of whose factors are colored left, and on the E (p) side only records all of whose factors are colored right. Group the retained records by target and by the number of prime factors. Every factor on the first side now has the left color, while every factor on the second side has the right color, so their sets of factors are disjoint and only one record is needed for each target and each possible number of factors. Fix a (d, +1)-structure with d ∈ Dp and a factorization from Lemma 5.1. The probability that all k factors receive the prescribed colors is 2−k . With R = 2k log 4 (58) independent colorings, the two chosen factors are placed on the required sides with probability at least 3/4. Because the lists of isogenies are reused, each new coloring requires only a scan of their records and new hash tables. Before accepting a proposed match, the algorithm checks each quotient map in the two chains, verifies the isomorphism between the targets on their curve equations, and checks both sets of factors. Opposite colors make these sets disjoint, and their union must contain k primes; the composite is therefore a separable isogeny of squarefree degree in Dp with cyclic kernel. These checks operate directly on the stored chains, with a rational map of degree p1/3+o(1) represented compositionally. Since 4B < p, Proposition 2.7 shows that the composite has sign +1. A failed matching attempt triggers a restart, while every returned map has passed all checks. Algorithm 2 A separable isogeny to the conjugate Require: A normalized supersingular model E/Fp2 Ensure: A separable cyclic isogeny φ : E → E (p) defining a (d, +1)-structure for some d ∈ Dp , or ⊥ 1: construct s, k, Q, Q, B, L from (34), (35), and (36) 2: L ← ListIsogenies(E, L, Q) (p) 3: R ← ListIsogenies(E k , L, Q) 4: for r = 1, . . . , 2 log 4 do 5: independently color every q ∈ Q left or right 6: make a hash table containing one record (κ(C), C, a, S, λ) ∈ L for every key (κ(C), a) with all primes in S colored left 7: for all (κ(C ′ ), C ′ , b, T, ρ) ∈ R with all primes in T colored right do 8: if the table contains a record with key (κ(C ′ ), k − b) then 9: retrieve (κ(C), C, k − b, S, λ) and an isomorphism ιC : C → C ′ 10: φ ← ρb ◦ ιC ◦ λ 11: if both chains and ιC verify, and |S| + |T | = k then 12: return φ 13: return ⊥
5.5
Complexity
Equations (42), (43), and the definition of Q give p L2 ≤ 4QB = p1/3 exp O( log p log log p) , p 2k = exp O( log p/ log log p) , p poly(Q, n) = exp O( log p log log p) . Consequently one trial at a sampled curve, including all colorings, costs p p1/3 exp O( log p log log p)
(59)
José Luis Delgado
21
time and at most the same amount of memory. The O(n4 ) expected trials from (55) are absorbed by the displayed bound.
5.6
Endomorphism construction
For a recovered conjugate isogeny define αE = πE (p) ◦ φ ∈ End(E) \ Z.
(60)
Its inseparable degree is p, whereas the valuation at p of the inseparable degree of a scalar multiplication is even; hence αE is non-scalar. Let ω : E⋆ → E be the separable part of the sampled walk, including the final isomorphism to the fixed model. Then α⋆ = ω b ◦ αE ◦ ω ∈ End(E⋆ ) \ Z
(61)
is non-scalar: after division by the central scalar deg ω, it is the conjugate of αE in End0 (E⋆ ). If the walk contains r ≤ T nontrivial steps, then deg α⋆ = 22r p deg φ ≤ 22T pB,
5.7
log deg α⋆ = O(n).
(62)
Output representation
Lemma 5.2 (Representation of the recovered map). The chain representing φ can be converted, within the time bound (59), to an efficient representation, and consequently ν −1 ◦ α⋆ ◦ ν has an efficient representation of polynomial length in n. Proof. Let d = deg φ. IsogenyInterpolation requires an integer N > d that is coprime to pd, bases for the components of E[N ] at each prime, and their images under φ [HLMW25, Proposition 2]. We can choose such a squarefree integer N with log N = O(n),
P + (N ) = O(n),
(63)
where P + denotes the largest prime factor. To construct N , take the product of the primes up to Cn, for a sufficiently large absolute constant C, and remove the primes that divide pd. Chebyshev’s estimates [RS62] show that the logarithm of the original product is linear in Cn, whereas the removed primes have total logarithm at most log(pd) = O(n); increasing C therefore leaves a product larger than d. On a maximal model, the Frobenius of degree p2 is the scalar −p. For each prime ℓ | N , a basis of E[ℓ] is therefore defined over an extension of degree at most ℓ − 1 = O(n) and can be computed in time polynomial in n and ℓ; compare [HLMW25, Lemma 6]. Evaluate the stored chain for φ on these bases, and then invoke IsogenyInterpolation. There are only polynomially many basis points, so the evaluations multiply the search cost by a polynomial in n. The interpolation is polynomial in its input length and in P + (N ), and both costs are absorbed by (59). The map πE (p) , the O(n) factors of degree two in ω and ω b , and the bounded degree isomorphisms ν, ν −1 all have efficient evaluators. Composing these evaluators with the representation of φ gives an efficient representation of ν −1 ◦ α⋆ ◦ ν. All operations use the input curve, the stored chains, finite-field arithmetic, and IsogenyInterpolation.
22
The supersingular isogeny problem
Algorithm 3 A non-scalar endomorphism Require: A supersingular elliptic curve Ein /Fp2 Ensure: A non-scalar αin ∈ End(Ein ) \ Z in efficient representation 1: n ← ⌊log2 p⌋ + 1 and compute T from (54) 2: if j(Ein ) = 0 or 1728 then 3: return an explicit automorphism of order 3 or 4 4: compute the maximal model E⋆ and the isomorphism ν : Ein → E⋆ from (51) 5: loop 6: take a lazy 2-isogeny walk ω : E⋆ → E of length T , retaining its chain 7: if j(E) = 0 or 1728 then 8: continue replace E by the fixed normalized model of its invariant and append the corre9: sponding isomorphism to ω 10: φ ← IsogenyToConjugate(E) 11: if φ ̸= ⊥ then 12: convert φ to an efficient representation using Lemma 5.2 13: αE ← πE (p) ◦ φ 14: α⋆ ← ω b ◦ αE ◦ ω 15: αin ← ν −1 ◦ α⋆ ◦ ν 16: return αin Theorem 5.3 (Main algorithm). There is a classical Las Vegas algorithm which, given a supersingular elliptic curve Ein /Fp2 , returns a non-scalar endomorphism αin ∈ End(Ein )\Z in efficient representation in expected time and memory p p1/3 exp O( log p log log p) = p1/3+o(1) . (64) The output satisfies log deg αin = O(log p), and the analysis is unconditional and independent of smoothness or statistical independence heuristics. Proof. The two special invariants terminate in polynomial time, and Section 5.1 reduces every other input to a generic maximal model without changing the asserted exponent. Theorem 4.4 and the mixing estimate give the success probability (55). Conditional on reaching a curve in the set from Theorem 4.4, choose one supported (d, +1)-structure and split its degree as in Lemma 5.1. Algorithm 1 contains the two isogenies determined by this split, and the analysis of the coloring step shows that Algorithm 2 recovers a valid match with probability at least 3/4. Every returned map passes the deterministic checks described above, while an unsuccessful coloring or sampled curve causes repetition, so correctness is deterministic. Equation (59) and the polynomial expected number of trials give (64). Equations (60)–(62) prove that the output of Algorithm 3 is a non-scalar endomorphism of the original curve, and Lemma 5.2 gives the required efficient representation. The density theorem assumes n ≥ 216 , leaving only finitely many smaller input sizes. An exhaustive search in the supersingular isogeny graph handles them, and enlarging the absolute constant in the O( · ) notation absorbs their cost, proving the theorem for every prime p > 3. Corollary 5.4. The supersingular endomorphism ring problem and the supersingular isogeny problem admit classical probabilistic algorithms with the same p1/3+o(1) time and memory bound. Proof. Equation (62) solves the bounded problem OneEndλ with λ(n) = O(n). The reduction from EndRing to bounded OneEnd of Page–Wesolowski and the unconditional equivalences of Herlédan Le Merdy–Wesolowski [PW24, Theorem 7.1][HLMW25,
José Luis Delgado
23
Theorem 1.1] have overhead polynomial in n and λ(n), which is absorbed by (64). This corollary concerns Isogeny with unrestricted output degree; a path whose prime degree is prescribed in advance lies outside its statement.
6
Conclusion
We have proved an unconditional p1/3+o(1) bound for the time and memory of OneEnd; the known reductions give the same bound for EndRing and Isogeny. This result attains the exponent 1/3 without the smoothness assumption used in the previous algorithm. The main step is the collision bound of Theorem 3.5. Two isogenies from one curve to its conjugate determine oriented embeddings of quadratic orders, and squarefree degrees prevent a path from descending and then ascending at the same conductor prime, so the embeddings can be compared inside a common order. The possible coincidences lie in a fiber of the square map on its class group, controlled by the 2-torsion, while primes shared by the two degrees contribute the factor Y 3 1+ . ℓ ℓ|gcd(d,e)
This collision bound turns the Chenu–Smith count into a statement about many distinct curves. Because the degree family is chosen before sampling and every degree in it is a product of small primes, the algorithm can enumerate the required isogenies from their known factorizations. Potential refinements concern the constants and memory use: a more detailed analysis of ideals above 2 and of ambiguous forms would reduce the constant in the collision bound, while a different method for matching the two lists might reduce the p1/3+o(1) memory requirement, with both changes preserving the unconditional exponent established here.
References [AOV26]
Yves Aubry, Roger Oyono, and Christelle Vincent. Minimal degree of an isogeny between a supersingular elliptic curve and its conjugate, 2026. URL: https://arxiv.org/abs/2607.14624, arXiv:2607.14624.
[AYZ95]
Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM, 42(4):844–856, 1995. doi:10.1145/210332.210337.
[Cox13]
David A. Cox. Primes of the Form x2 + ny 2 : Fermat, Class Field Theory, and Complex Multiplication. John Wiley & Sons, Inc., Hoboken, NJ, second edition, 2013. doi:10.1002/9781118400722.
[CS22]
Mathilde Chenu and Benjamin Smith. Higher-degree supersingular group actions. Transactions on Mathematical Cryptology, 1(2):85–101, 2022. URL: https://journals.flvc.org/mathcryptology/article/view/130604, arXiv:2107.08832.
[HLMW25] Arthur Herlédan Le Merdy and Benjamin Wesolowski. Unconditional foundations for supersingular isogeny-based cryptography. In Theory of Cryptography – TCC 2025, Part III, volume 16270 of Lecture Notes in Computer Science, pages 266–297, 2025. doi:10.1007/978-3-032-12296-4_9. [Onu21]
Hiroshi Onuki. On oriented supersingular elliptic curves. Finite Fields and Their Applications, 69:101777, 2021. URL: https://arxiv.org/abs/2002.0 9894v3, arXiv:2002.09894, doi:10.1016/j.ffa.2020.101777.
24
The supersingular isogeny problem
[PW24]
Aurel Page and Benjamin Wesolowski. The supersingular endomorphism ring and one endomorphism problems are equivalent. In Advances in Cryptology – EUROCRYPT 2024, Part VI, volume 14656 of Lecture Notes in Computer Science, pages 388–417, 2024. doi:10.1007/978-3-031-58751-1_14.
[RS62]
J. Barkley Rosser and Lowell Schoenfeld. Approximate formulas for some functions of prime numbers. Illinois Journal of Mathematics, 6(1):64–94, 1962. doi:10.1215/ijm/1255631807.
[Tat51]
Tikao Tatuzawa. On a theorem of Siegel. Japanese Journal of Mathematics: Transactions and Abstracts, 21:163–178, 1951. doi:10.4099/jjm1924.21.0 _163.
[Udo26]
Aleksei Udovenko. Solving the supersingular isogeny problem in time p2/5+o(1) using bivariate multipoint evaluation. Cryptology ePrint Archive, Paper 2026/1575, 2026. URL: https://eprint.iacr.org/2026/1575.
[Voi21]
John Voight. Quaternion Algebras, volume 288 of Graduate Texts in Mathematics. Springer, Cham, 2021. URL: https://jvoight.github.io/quat.html, doi:10.1007/978-3-030-56694-4.
[Wes26]
Benjamin Wesolowski. The supersingular isogeny problem in time and memory p1/3+o(1) . Cryptology ePrint Archive, Paper 2026/1486, 2026. URL: https: //eprint.iacr.org/2026/1486.