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

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.