Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper investigates a memetic algorithm for searching supersingular elliptic curves over the prime field $\mathbb{F}_p$, addressing the challenges posed by the sparse distribution of such curves. By employing a one-dimensional $j$-invariant chromosome and optimizing through adaptive mutation and local search under the NonMultiplicity Distance (NMD) objective, the algorithm successfully identifies an exact supersingular curve at 46 bits and achieves near-supersingular curves with minimal Frobenius trace deviations. The findings highlight the effectiveness of NMD-driven search strategies in navigating the complex landscape of $\mathbb{F}_p$ for isogeny-based cryptography.
Memetic search techniques can uncover exact and near-supersingular elliptic curves in the sparse landscape of $\mathbb{F}_p$, achieving unprecedented precision in Frobenius trace deviations.
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.