Source-linked AI summary
Smoothness of Shortest Isogenies to Frobenius Conjugates
Yi Ouyang, Wei Wei, Zheng Xu
TL;DR
The paper asks how often the least isogeny degree from a supersingular elliptic curve to its Frobenius conjugate is smooth. It proves the relevant smoothness result, establishing Wesolowski’s heuristic and supporting his attack without that heuristic assumption.
Problem
Wesolowski’s attack depends on the heuristic that the least isogeny degree δ_E has smoothness like a uniformly random integer of comparable size.
Source: §1 · p. 2Method
The paper proves a theorem on the smoothness of δ_E and applies it to establish Wesolowski’s heuristic.
Source: §1 · p. 2Results
Heuristic W is true.
Source: §6.1 · p. 21Takeaways & Limitations
The smoothness result removes the heuristic assumption from the justification of Wesolowski’s p^1/3+o(1) attack.
Source: §1 · p. 2, §6.1 · p. 21The stated uniformity applies when (log p)^ε < u < (log p)^(1−ε), for fixed ε.
Source: §1 · p. 2
Abstract
from arXiv · showhide
Let $E$ be chosen uniformly from the geometric isomorphism classes of supersingular elliptic curves over $\overline{\mathbb{F}}_p$ and $\delta_E$ be the minimum degree of isogenies from $E$ to its Frobenius conjugate $E^{(p)}$. We prove the smoothness of $\delta_E$ and hence affirm Wesolowski's $p^{1/3+o(1)}$ attack on the supersingular endomorphism ring problem is unconditional.
1. Introduction
The paper studies the least isogeny degree from a supersingular elliptic curve to its Frobenius conjugate and proves its smoothness. This establishes the smoothness premise behind Wesolowski’s attack unconditionally.
1. Introduction
- The paper asks how often the least degree δ_E is B-smooth, equivalently how its largest prime factor P+(δ_E) is distributed.Smooth-degree isogenies can be computed as compositions of low-degree isogenies.Source: §1 · p. 2
- Wesolowski’s p^1/3+o(1) attack relies on finding a B-smooth isogeny from E to E^(p), an assumption the paper’s main theorem implies.Composing that isogeny with Frobenius gives a non-scalar endomorphism of E.Source: §1 · p. 2
- The heuristic models δ_E’s smoothness using a uniformly random integer of comparable size and specifies an asymptotic range for its parameter.The stated uniformity range is (log p)^ε < u < (log p)^(1−ε), for fixed ε.Source: §1 · p. 2
- Theorem 1.1 proves the main smoothness result, which the authors state implies Wesolowski’s heuristic.Its constants depend only on ε, for fixed ε in (0, 1/2).Source: §1 · p. 2
- Earlier work bounded the number of curves admitting short paths between Frobenius-conjugate vertices, while later work studied extremal degrees and related settings.Aubry, Oyono, and Vincent showed the exponent 1/3 is asymptotically optimal.Source: §1 · p. 2
- The paper proves upper and lower bounds using number-theoretic arguments, with Section 5 identified as its technical heart.It first develops smooth-number, class-number, and Brandt-operator preliminaries.Source: §1 · p. 3
Declaration of AI use.
The authors disclose using ChatGPT-5.6 Sol to assist with mathematical arguments and derivations, which they independently verified.
Declaration of AI use.
- The authors used ChatGPT-5.6 Sol to assist in developing mathematical arguments and derivations, and report independently verifying all AI-assisted results and proofs.They state that they take full responsibility for the paper’s accuracy and integrity.Source: Declaration of AI use · p. 3
2. Notation and preliminaries
The preliminaries fix notation and establish tools for counting smooth numbers and relating imaginary quadratic orders to their class numbers.
2.1. Notations and conventions.
- The paper takes p ≥ 5 prime, treats curves and isogenies geometrically unless specified, and uses the uniform measure on supersingular isomorphism classes.An integer n is B-smooth exactly when its largest prime factor P+(n) is at most B.Source: §2.1 · p. 3
2.2. Counting smooth numbers. \b
- The paper defines the Dickman-de Bruijn function by its delay differential equation and uses uniform estimates to count smooth numbers in the stated parameter range.It also estimates squarefree B-smooth integers in an interval using local-density and local-ratio results.Source: §2.2 · pp. 3–5
2.3. Class number formula of imaginary quadratic orders.
- The class-number preliminaries use discriminants of imaginary quadratic orders and bound associated L-values, allowing at most one exceptional discriminant in the stated family.For the selected squarefree integers n, the discriminant construction is injective and yields fundamental discriminants.Source: §2.3 · pp. 6–7
3. Counting connection isogenies
The section relates supersingular curves to quaternionic ideal classes, then uses Brandt operators and a trace formula to count primitive connection isogenies to Frobenius conjugates.
3.1. Basic of supersingular elliptic curves.
- Deuring’s theorem identifies supersingular geometric classes with locally principal left ideal classes of a maximal order in the quaternion algebra ramified at p and infinity.The right order associated with a curve is isomorphic to its endomorphism ring.Source: §3.1 · p. 7
3.2. Brandt operators.
- For n ≥1, the Brandt operator is a Z-linear operator whose matrix records degree-n isogeny correspondences among supersingular isomorphism classes.When (n, p) = 1, the matrix entries count isogenies modulo postcomposition by automorphisms of the target.Source: §3.2 · p. 8
- At p, the unique subgroup of order p is the kernel of relative Frobenius, so the ramified Brandt operator permutes classes by Frobenius conjugation.Every supersingular j-invariant is defined over Fp2.Source: §3.2 · pp. 8–9
3.3. Primitive connection isogenies.
- A connection isogeny is primitive if it is not an integer multiple of another isogeny; any minimal-degree connection is primitive.The section counts such isogenies using their orbits under target automorphisms.Source: §3.3 · p. 10
- For n < p/4, the trace parameter must be t = 0: p divides t, while the trace-formula bound gives |t| < p.At p, the corresponding element lies in the maximal two-sided ideal, whose reduced traces are divisible by p; the resulting local optimal-embedding factors are all 1.Source: §3.3 · pp. 10–11
4. Proof of the upper bound
The section proves an upper bound by relating the minimum degree to counts of primitive connection isogenies and then applying a smooth-number estimate.
4. Proof of the upper bound
- For fixed 0 < ε < 1/2, the upper-bound proposition applies to B in the stated range L^ε < u < L^(1−ε), for sufficiently large p.Its proof uses that a shortest connection is primitive and δ_E ≤ N, averages primitive-isogeny counts, and applies a smooth-number lemma; the stated scale is N ≍ p^(1/3).Source: §4 · pp. 11–12
5. Proof of the lower bound
The section proves a lower bound for the probability that the shortest connection degree is B-smooth, using counts of selected isogenies and predecessor pairs. It turns pairs of primitive connection isogenies into quaternion orders and applies local counts of maximal orders containing them, identifying the shortest primitive connection as the first root in the chosen ordering.
5.1. Quaternionic pairs estimate.
- Each ordered pair of distinct primitive connection isogenies determines a triple (m, n, t) and an order R with reduced discriminant p²(4mn − t²).The relations i² = −pm, j² = −pn, and ij + ji = −pt determine the order’s multiplication table.Source: §5.1 · p. 12
- For fixed (m, n, t), admissible isogeny pairs over a curve with endomorphism ring M are bounded by embeddings of R into M.The count is organized by maximal-order classes and their overorders, reducing pair counting to bounding the number of maximal overorders of R.Source: §5.1 · pp. 13–14
5.2. Counting maximal overorders.
- For B_q(R), the cited result is diam B_q(R) ≤ e_q; in particular, when e_q=0, B_q(R) consists of a single vertex.Source: §5.2 · p. 15
- For squarefree n and 1 ≤ m, n < p/4, the theorem bounds maximal overorders using local counts, with D = 4mn − t² > 0.For q ≠ 2, p with e_q > 0, the stated local bound is #B_q(R) ≤ 3(e_q + 1)q^⌊g_q/2⌋; at q = 2, #B_2(R) ≤ 6(e_2 + 1).Source: §5.2 · pp. 16–18
- Squarefreeness of n forces the quadratic-order stem bound to simplify for q ≠ 2, p, while the 2-adic count is at most 6(e_2 + 1).The local counts are combined by a product formula over finite primes to obtain the global maximal-overorder count.Source: §5.2 · pp. 17–18
- The maximal-overorder count concludes by combining Theorem 5.5 with Lemma 5.6.The preceding counting steps place m in one residue class modulo d/g and use d ≤ 2n.Source: §5.2 · pp. 18–19
5.3. Bound of E(SE) and E(PE).
- Proposition 5.9 specifies uniformity for all sufficiently large p over B satisfying Lε < u < L1−ε, for fixed 0 < γ ≤ 1 and 0 < ε < 1/2.Source: §5.3 · p. 20
5.4. Proof of the lower bound.
- For each curve, 1P +(δE) ≥ SE − PE: the first root has degree δE, and if it is selected, every other selected root has a distinct predecessor.If the first root is not selected, every selected root has it as a distinct predecessor, so SE − PE ≤ 0.Source: §5.4 · p. 21
- Proposition 5.11 gives a lower bound for Pr(P +(δE) ≤ B) for sufficiently large p and admissible B.The stated bound uses the constants from Propositions 5.8 and 5.9.Source: §5.4 · p. 21
6. Probabilistic Consequences and Cryptanalytic Applications
The paper derives Wesolowski’s heuristic from its result, making the p^1/3+o(1) attack unconditional. It also identifies a broader success event that can include non-minimal connecting isogenies.
6.1. Proof of Wesolowski’s heuristic.
- Wesolowski’s heuristic follows from the paper’s result, so his p^1/3+o(1) attack no longer relies on that heuristic assumption.The section states this as the consequence of Theorem 6.1.Source: §6.1 · p. 21
6.2. A higher success probability.
- The attack’s success event can include a B-smooth connecting isogeny that is not of minimal degree.The section says success is not restricted to the case where the minimal connecting degree δ_E is B-smooth.Source: §6.2 · p. 22
- The Frobenius-claw event corresponds to this broader event, and its success probability may be strictly larger because non-minimal connecting isogenies can also be used.The comparison is stated after disregarding finite-p deviations from the limiting distribution.Source: §6.2 · p. 22
- To obtain a sharper lower bound for success probability, the argument replaces the minimal-degree restriction with a cumulative set of smooth degrees.The earlier set was tailored to counting minimal connecting isogenies; the cumulative set is used when minimality is unnecessary.Source: §6.2 · p. 22