Skip to content
Preprint

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

Sep 2026 · 0 citations · 24 references
Computer Science

TL;DR

These results demonstrate that NMD-driven memetic search effectively navigates the sparse $\mathbb{F}_p$ landscape and systematically locates near-supersingular structures.

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.

View source

Similar papers

Preprint Sep 2026

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

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...

J. L. Delgado · 0 citations
Preprint Sep 2026

Number fields as curves over $\mathbf{F}_1$

We study function fields in one variable over the field with one element $\mathbf{F}_1$. It is proved that the Galois extensions of $\mathbf{Q}$ are isomorphic to the curves over $\mathbf{F}_1$ being understood as the Deitmar schemes. Specifically, one gets explicit formulas linking the genus and the number of cusps of...

Igor V. Nikolaev · 0 citations
Preprint Sep 2026

Abelian $p$-extensions with restricted $p$-ramification and the cyclotomic $\mathbb{Z}_2$-extension of $\mathbb{Q} (\sqrt{q})$

We develop Hachimori's study on the unramified Iwasawa modules using extensions with restricted $p$-ramification. Let $K$ be an algebraic number field, and $p$ a prime number which splits into two distinct primes $\mathfrak{p}$, $\mathfrak{p}'$ in $K$. Assume that $K$ and $p$ satisfies several (somewhat strict) conditi...

T. Itoh, N. Kumakawa · 0 citations
Preprint Sep 2026

Fields of definition of $p$-torsion points of elliptic curves and their ramification

Let $E$ be an elliptic curve over $\mathbb{Q}_p$. We study the field $\mathbb{Q}_p(E[p])$ generated by the $p$-torsion points of $E$. When $E$ has good reduction, we determine not only $\mathbb{Q}_p(E[p])$ but also the field $\mathbb{Q}_p(P)$ for every point $P\in E[p]$. This classification yields criteria for the exis...

Yoshiyasu Ozeki, Manabu Yoshida · 0 citations
Preprint Sep 2026

Computing the Iwasawa $\mu$-Invariants for Elliptic Curves over $\mathbb{Z}_2$-Extensions

Let $E$ be an elliptic curve defined over rational numbers. Further assume $E$ has good ordinary reduction at $p=2$ and $E[4]$ is reducible as a $G_\mathbb{Q}$-representation. In this paper, we offer sufficient and necessary computational criteria for the algebraic Iwasawa $\mu$-invariant over the cyclotomic $\mathbb{Z...

Zi-Chao Lin, Mu-Lun Yin · 0 citations
Preprint Oct 2026

Fuglede's conjecture holds in $\mathbb{F}_{p}^{d}$ for $p=2,\,d=8$ and $p=11,\,d=3$

Fuglede's conjecture in $\mathbb{F}_p^d$ says that a nonempty set tiles by translation if and only if it is spectral. We prove the conjecture in $\mathbb{F}_2^8$ and $\mathbb{F}_{11}^3$. Over $\mathbb{F}_2$ we show more generally that the Fourier support of a nonconstant indicator of density different from one half con...

S. Ferguson, J. Iosevich · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.