CS Paper Radar

Memetic Search for Supersingular Elliptic Curves over $\mathbb{F}_p$

Ismel Martínez-Díaz

cs.CR ·submitted 2026-09-03 01:11 UTC · v1
unusual

Abstract

The search for supersingular elliptic curves is a fundamental computational problem in isogeny-based cryptography. A recent metaheuristic formulation over $\mathbb{F}_{p^2}$ introduced the NonMultiplicity Distance (NMD) objective, measuring the deviation of the Frobenius trace from a multiple of $p$, and showed that uninformed random search fails beyond $\approx 10^{13}$ candidates. This work investigates metaheuristic search over the prime field $\mathbb{F}_p$, the setting for oriented isogeny protocols such as CSIDH, OSIDH, and SQISign. Although the candidate space decreases from $p^2$ to $p$, the supersingular locus is asymptotically sparse ($O(\sqrt{p}\log p)$ curves), keeping the search exponentially difficult. We formulate a memetic algorithm tailored to $\mathbb{F}_p$ using a one-dimensional $j$-invariant chromosome, bit-level recombination, adaptive mutation, and periodic local search under the NMD objective. Benchmarks across 30 independent seeds at 40-bit, 46-bit, and 51-bit prime sizes ($p \approx 1.13\times 10^{15}$) show that the algorithm discovers an exact supersingular curve at 46 bits and consistently converges to ``near-supersingular'' ordinary curves with Frobenius traces remarkably close to zero: best NMD values of 19 at 40 bits and 3 at 51 bits, corresponding to relative trace deviations of $1.3\times 10^{-5}$ and $4.5\times 10^{-8}$ across the Hasse interval. These results demonstrate that NMD-driven memetic search effectively navigates the sparse $\mathbb{F}_p$ landscape and systematically locates near-supersingular structures.

Closest papers

Nearest neighbours by meaning across the whole index.

The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally

cs.CR ·2026-09-18 ·José Luis Delgado
similarity 0.72
Abstract

Given a supersingular elliptic curve $E/\mathbb{F}_{p^2}$, the $\mathsf{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. Wesolowski 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^{1/3}\exp\bigl(O(\sqrt{\log p\,\log\log p})\bigr) = p^{1/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.

0.16

Supersingularity and Superspeciality Verification of Abelian Surfaces

cs.CR math.NT ·2026-10-01 ·Maria Corte-Real Santos, Gioella Lorenzon, Krijn Reijnders
similarity 0.66
Abstract

Supersingular abelian surfaces are essential in isogeny-based cryptography. Despite this, we have no efficient algorithm to verify if a given abelian surface is supersingular. In this work, we initiate this research topic by giving an efficient Monte Carlo algorithm to verify if an abelian surface over $\mathbb{F}_p$ is supersingular in $O(\log p)$ with negligible failure probability, and an efficient conclusive algorithm if the order is smooth. We derive this algorithm by a careful analysis on the structure of supersingular Jacobians over $\mathbb{F}_p$. Furthermore, we derive efficient algorithms to verify if an abelian variety of any dimension is minimal or maximal, and to verify if a Jacobian of any dimension is superspecial.

0.20

Deterministic Root-Finding over Finite Fields with Elliptic Curves

cs.SC cs.CCmath.NT ·2026-10-23 ·Pierre-Jean Spaenlehauer
similarity 0.63
Abstract

Finding the roots of a polynomial over a finite field $\mathbb F_q$ in deterministic polynomial time is a long-standing open problem. Classical deterministic methods work in the multiplicative group $\mathbb F_q^\times$ and are efficient only when $q-1$ is smooth, which is rarely the case. We propose a method that replaces $\mathbb F_q^\times$ by the groups of rational points of an elliptic curve $E$ and of its quadratic twist $\widetilde E$. The computation splits into an offline phase, which depends only on $\mathbb F_q$ and outputs a short \emph{elliptic preprocessing datum} $\mathcal D$, and an online phase, which processes the input polynomial. Writing $Ξ(\mathcal D)$ for the largest prime factor of $\lvert E(\mathbb F_q)\rvert\cdot\lvert\widetilde E(\mathbb F_q)\rvert$, the online phase is deterministic and finds the roots of any $f\in\mathbb F_q[X]$ of degree $n$ within $\widetilde O(Ξ(\mathcal D)^2\,n\log^2 q+n^ω\log q+n\log^3 q)$ operations in $\mathbb F_q$. A precursor of our method is an algorithm by Rónyai, which recovers the roots through Galois computations over number fields, relies on GRH, and comes with a polynomial bound of unspecified degree; in contrast, our online phase works entirely over $\mathbb F_q$ and is unconditional. Moreover, $\mathcal D$ can be certified deterministically and unconditionally in time polynomial in $\log q$ and $Ξ(\mathcal D)$. We conjecture that every $\mathbb F_q$ of large enough characteristic admits a datum with $Ξ(\mathcal D)\leq(\log q)^{O(1)}$, and support this with a heuristic and with experiments. Constructing such a datum in polynomial time remains open.

0.22

Smoothness of Shortest Isogenies to Frobenius Conjugates

cs.CR math.NT ·2026-10-15 ·Yi Ouyang, Wei Wei, Zheng Xu
similarity 0.61
Abstract

Let $E$ be chosen uniformly from the geometric isomorphism classes of supersingular elliptic curves over $\overline{\mathbb{F}}_p$ and $δ_E$ be the minimum degree of isogenies from $E$ to its Frobenius conjugate $E^{(p)}$. We establish bounds for the smoothness probability of $δ_E$ and hence affirm Wesolowski's $p^{1/3+o(1)}$ attack on the supersingular endomorphism ring problem is unconditional. We also establish a uniform asymptotic formula, with a main term expressed in terms of Dirichlet $L$ values, for the probability that a connection isogeny of degree $n$ exists between $E$ and $E^{(p)}$.

0.11

Supersingular Elliptic Curves Without Inseparable Small Degree Endomorphisms

cs.CR math.NT ·2026-09-03 ·Nicolas Swanson
theorycode/dataunusual similarity 0.59
Abstract · Computational supplement available at https://github.com/Nicswansonwaterloo/MaxFrobeniusConj

For a fixed characteristic $p$, let $δ(p)$ denote the smallest degree needed to guarantee the existence of an isogeny from any supersingular curve $E$ to its Frobenius conjugate $E^{(p)}$. We translate existence questions concerning $δ(p)$ into questions about positive definite integral ternary quadratic forms and use Voronoi's theory of perfect forms in dimension three to characterize when $δ(p)$ is nearly maximal. For sufficiently large primes, we show that $δ(p)$ attains its upper bound precisely when $p$ is represented by one of nine explicit cubic polynomials, reducing the infinitude of such primes to whether one of these cubics takes prime values infinitely often. We also prove that, for almost all primes, $δ(p)$ lies at least $p^{1/6-o(1)}$ below its upper bound.

0.68

Superspecial curves of genus two over prime fields: Frobenius types and rational (2,2)-kernels

cs.CR math.NTmath.AG ·2026-11-18 ·Hung Dang
similarity 0.58
Abstract · 55 pages, 9 tables. Code, logs and data: [Zenodo DOI, add after upload]

Superspecial curves of genus two over a prime field $\mathbb{F}_p$, and the rational $(2,2)$-isogenies between their Jacobians, are the vertices and edges of the graph on which genus-two isogeny-based cryptography is built. Let $C$ be such a curve, with Jacobian $J$ and Frobenius endomorphism $π$. We show that $π^2 = p\,α_*$ for a unique automorphism $α$ of $C$ over $\mathbb{F}_p$ whose action on the Weierstrass points is the square of that of Frobenius. For $p \ge 7$ this gives the list of Frobenius types of the Weierstrass points: eight types, each with its Weil polynomial, a congruence condition on $p$, and its number 15, 3, 3, 7, 1, 1, 3 or 1 of $\mathbb{F}_p$-rational $(2,2)$-kernels; when all Weierstrass points are rational, the 2-Tate pairing on $J[2]$ is determined by $p \bmod 8$. We then prove closed formulas, in terms of class numbers of imaginary quadratic orders and of $ζ_{\mathbb{Q}(\sqrt p)}(-1)$, for the mass of the curves of each type and for the mass of the rational kernels whose quotient is a product of elliptic curves. For $π^2 = \pm p$ the total masses are due to Ibukiyama and to Xue and Yu; our proofs use the 2-adic Tate modules, the symmetry of the Richelot correspondence and Eichler's mass formula, and, for the other curves, modules over orders of a quartic CM field. The kernels are counted through gluings of supersingular elliptic curves. As a consequence, the proportion of rational kernels with decomposed quotient is of order $p^{-1/2}(1+L(1,χ))$, where $χ$ is the quadratic character of $\mathbb{Q}(\sqrt{-p})$. All formulas agree with an exact enumeration for the 37 primes $7 \le p \le 173$. Finally we describe the graph of $\mathbb{F}_p$-rational Richelot isogenies, which is far from connected in the range computed, and discuss what these results say about its use in isogeny-based cryptography.

0.32

Asymptotically good codes from Siegel modular varieties

cs.IT math.NTmath.AG ·2026-11-10 ·Yota Maeda
theory similarity 0.53
Abstract · 26 pages, v2:Acknowledgments added

We construct asymptotically good codes by evaluating Siegel modular forms at superspecial points on congruence towers of Siegel modular varieties. For every genus $g\ge2$ and every fixed weight $w\ge g+1$, the construction gives such a family in sufficiently large characteristic, over a finite field which is independent of the level of the tower. The towers can be chosen so that this field is $\mathbb{F}_{p^2}$. We give an explicit lower bound for the asymptotic rate. The lower bound for the relative minimum distance follows from the Pieri formula on the space of flags in the Hodge bundle and an intersection argument along its strata. We also prove that, for $p\ge5$ and $0\le w\le p+1$, the kernel of evaluation in every genus consists precisely of the multiples of the ordinary Hasse invariant. For $g=2,3$, the geometry of the supersingular locus gives explicit bounds for the relative minimum distance and recovery sets whose sizes are bounded independently of the level.

0.17

A Polynomial-Time Attack on the McEliece Cryptosystem on Elliptic Codes with Arbitrary Divisors

cs.IT ·2026-09-15 ·Artyom Kuninets, Ekaterina Malygina, Evgeniy Melnichuk
theory similarity 0.53
Abstract

The McEliece cryptosystem based on algebraic geometry codes has been proposed as a way to reduce the key size of code-based cryptography, but several structural attacks have demonstrated the vulnerability of particular families of algebraic geometry codes. Despite this, until recently, there remained schemes and parameter sets that were not vulnerable to any known attack. We propose a new structural attack with ``hints'' that applies to elliptic codes with arbitrary effective divisors. In particular, we prove that, given the elliptic curve, the public generator matrix, and three points from the evaluation divisor, the entire divisor can be recovered in polynomial time, independently of the number of errors used in the cryptosystem. The attack requires $\mathcal{O}(k^2n^2+|\mathcal{E}(\mathbb{F}_q)|+n)$ operations in $\mathbb{F}_q$ and succeeds with overwhelming probability, after which the second divisor is recovered in $\mathcal{O}\!\left(k^2n^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ operations. We further propose an optimized version of the attack that requires no additional information at all. Exploiting the action of the automorphisms of the curve, the three known points are replaced by the enumeration of a single pair of field elements, which yields an equivalent key on the given public curve in $\mathcal{O}\!\left(k^2n^2 + q^2 + (|\mathcal{E}(\mathbb{F}_q)|-n)n^2\right)$ operations on average.

0.25