PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Ismel Martínez-Díaz

arXiv:2609.03249v1cs.CR

TL;DR

Finding supersingular curves over Fp remains difficult because the supersingular locus is sparse, despite the smaller candidate space. This paper adapts memetic search to Fp under the NMD objective. It finds an exact curve at 46 bits and near-supersingular ordinary curves at 40 and 51 bits.

  • Problem

    The Fp search space is smaller than Fp2, but its supersingular locus remains sparse, making uninformed search difficult.

    Source: §1.3 · p. 3, §3.1 · p. 6

  • Method

    The paper adapts a memetic algorithm to a one-dimensional Fp j-invariant search, using bit-level recombination, adaptive mutation, and periodic local search under NMD.

    Source: §1.4 · p. 4, §5 · p. 7

  • Results

    At 46 bits the algorithm found an independently verified supersingular curve; at 40 and 51 bits its best ordinary curves had |t| = 19 and |t| = 3, respectively.

    Source: §8 · p. 14

  • Takeaways & Limitations

    NMD-driven search over Fp systematically locates ordinary curves with traces close to zero as well as an exact supersingular curve in the tested benchmarks.

    Source: §1.4 · p. 4, §8 · p. 14

    The 40-, 46-, and 51-bit primes are computational benchmarks, not production parameters, and cannot be used for post-quantum security.

    Source: §7.3 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

The introduction places supersingular curves in post-quantum isogeny cryptography, describes the challenge of finding them, and motivates searching over Fp for oriented protocols. It presents an Fp-specific memetic algorithm and benchmarks it at scales up to about 10^15 candidates.

1.1 Historical Context and the Post-Quantum Paradigm

  • Quantum algorithms threaten classical public-key systems, prompting post-quantum alternatives that include isogeny cryptography and prime-field group-action protocols.The introduction recounts the break of SIDH and SIKE through auxiliary torsion-point information, while noting that the fundamental problem of computing supersingular isogenies was left uncompromised.Source: §1.1 · p. 2

1.2 The Challenge of Supersingular Curve Generation

  • Deterministic CM-based construction methods exist, but require computing class polynomials whose degrees grow with the class number.Earlier Fp2 metaheuristic work introduced NMD, found random search ineffective beyond roughly 10^13 candidates, and observed searches tending toward ordinary curves with traces close to zero.Source: §1.2 · p. 3

1.3 Motivation and Shift to the Prime Field Fp

  • Even over Fp, the supersingular hit probability is O(log p/√p), so the search remains a needle-in-a-haystack problem at cryptographically relevant sizes.The introduction contrasts the p^2 candidate space and approximately p/12 supersingular invariants over Fp2 with the p candidates and O(√p log p) Fp-rational supersingular invariants.Source: §1.3 · p. 3
  • Fp-rational supersingular curves provide the starting curves required by oriented protocols, while Fp2 curves cannot directly serve that role.The paper also identifies a one-dimensional j-invariant search space with integer neighborhoods, bit-level recombination, and a direct notion of distance.Source: §1.3 · p. 3

1.4 Contributions and Paper Organization

  • The contribution adapts memetic search to Fp and reports an independently verified supersingular curve at 46 bits, plus ordinary curves with |t| = 19 and |t| = 3 at 40 and 51 bits.The latter are quantified relative to the Hasse interval; the search uses 30 independent seeds per configuration.Source: §1.4 · p. 4

2 Background and Preliminaries

This section establishes the curve and algorithmic background for the search: elliptic curves over Fp are described through their Frobenius traces, and memetic algorithms combine evolutionary exploration with local refinement.

2.1 Elliptic Curves and the Frobenius Trace

  • The section introduces elliptic curves in short Weierstrass form and uses the j-invariant to classify curves up to isomorphism over the algebraic closure.It supplies canonical curve representatives for j outside 0 and 1728 and identifies those two boundary cases separately.Source: §2.1 · pp. 4–5
  • For E/Fp, the Frobenius trace governs the point count, and supersingularity is characterized by t ≡ 0 (mod p); the endomorphism rings distinguish supersingular from ordinary curves.For supersingular curves End(E) is a maximal order in a definite quaternion algebra, while the Fp-rational endomorphism ring is an order in Q(√−p).Source: §2.1 · p. 5

2.2 Memetic Algorithms

  • Memetic algorithms combine population-based evolutionary exploration with problem-specific local refinement; their operators maintain diversity while local search intensifies promising regions.The background notes that these methods can outperform genetic algorithms and random sampling on complex or deceptive landscapes.Source: §2.2 · p. 5

3 Search Space and Problem Formulation

The section contrasts Fp2 and Fp search spaces, motivates the prime-field setting for oriented protocols, and selects progressively larger primes to test the algorithm beyond the scale where prior random search stagnated.

3.1 Comparison: Search over Fp2 vs. Fp

  • Table 1 compares search-space size and supersingular-invariant density: Fp2 has p^2 candidates and ⌊p/12⌋+ ε supersingular invariants, while Fp has p candidates and O(√p log p) Fp-rational invariants.The Fp bound is attributed to Delfs and Galbraith.Source: §3.1 · p. 6, Table 1 · p. 6
  • Searching over Fp gives a one-dimensional j-space, removing extension-field representation overhead and providing a natural integer metric for mutation and local search.The same choice aligns with oriented schemes that require Fp-rational supersingular public starting curves.Source: §3.1 · p. 6
  • At a 46-bit prime, the Fp supersingular density is on the order of 10^-6, so uninformed random search requires millions of point counts and succeeds only by chance within feasible budgets.The search probability is described as vanishingly small for large primes despite being relatively higher than over Fp2.Source: §3.1 · p. 6

3.2 Experimental Benchmark Selection

  • Prior work observed naive random search stagnating beyond approximately 10^13 candidates; this study adds a more challenging prime beyond that regime.The validation strategy follows the earlier work's escalating benchmark approach.Source: §3.2 · p. 6
  • The 46-bit prime places the search space directly at the 3.52 × 10^13 candidate scale used as the primary benchmark, while the 51-bit prime (p ≈ 1.13 × 10^15, about 32× larger) tests memetic-search degradation.Source: §3.2 · p. 6
  • The benchmark set uses three primes, all congruent to 3 modulo 4, so the j = 1728 supersingular boundary case is handled uniformly.The selected prime parameters are listed in Table 2.Source: §3.2 · p. 7, Table 2 · p. 7

4 Objective Function

The objective minimizes NonMultiplicity Distance over canonical curve representatives. For the prime sizes considered, that quantity reduces to absolute Frobenius trace, and zero fitness identifies supersingularity.

4 Objective Function

  • The paper retains the previously introduced NMD objective unchanged and formulates the search as its minimization over canonical curve representatives.The representative curve is defined in equation (3).Source: §4 · p. 7
  • A fitness value of zero means t ≡ 0 (mod p), which is necessary and sufficient for supersingularity when p > 3.The objective uses the Frobenius trace t = p + 1 − #E(Fp).Source: §4 · p. 7
  • For p > 16, the Hasse bound makes NMD equal to |t|, so the objective directly measures absolute Frobenius trace on the scale of the Hasse interval.The stated bound is |t| ≤ 2√p < p/2.Source: §4 · p. 7

5 Proposed Memetic Approach

The method places its memetic-search population directly in Fp, adapting chromosome evaluation and evolutionary operators to this one-dimensional representation.

5.1 Chromosome Representation and Evaluation

  • Each chromosome is a single Fp element evaluated by constructing its canonical curve, point-counting over Fp, determining the trace, and computing NMD.The initial population is sampled uniformly without replacement from Fp.Source: §5 · p. 7, §5.1 · p. 8

5.2 Evolutionary Operators

  • Crossover swaps a uniformly chosen bit interval between binary parent chromosomes, then reduces the resulting integer modulo p.This enables recombination over single finite-field elements.Source: Bit-Wise Recombination (Crossover) · p. 8, §5.2 · p. 8
  • Mutation adds a random offset modulo p, with a linearly shrinking radius that moves from global exploration toward local refinement.The schedule runs from rinit = floor(p/4) to rfinal = floor(p/216).Source: Adaptive Neighborhood Mutation · p. 8
  • Tournament selection uses groups of three, while the best Nelite individuals carry over unchanged to the next generation.Source: Selection and Elitism · p. 8
  • Every 10 generations, local search explores neighborhoods around elite candidates, halves the radius after unsuccessful rounds, and greedily accepts improvements.Source: Local Search Exploitation · p. 8

6 Experimental Evaluation and Results

Across 30 seeds per configuration, the evaluation compares uniform random sampling with the memetic algorithm at three prime sizes, verifies one exact supersingular curve, and examines near-supersingular ordinary curves. The results show strong best-run performance at larger primes alongside weaker average per-run performance for the memetic algorithm.

6.1 Experimental Configuration

  • Each configuration used 30 random seeds; an MA run used approximately 11,780 curve evaluations, slightly above the random baseline's 10,000.The experiments used three primes listed in Table 2.Source: §6.1 · p. 9, Table 3 · p. 9

6.2 Empirical Comparison and Success Rates

  • At 46 and 51 bits, the best memetic runs reached NMD 0 versus 80 and NMD 3 versus 310 for random search; at 40 bits, random search found one exact curve while MA's best NMD was 19.The comparison covers 30 independent runs per configuration.Source: Table 4 · p. 10, §6.2 · p. 10
  • Random search had better mean and median per-run best NMD at all three primes, with the MA mean 3.5× the random mean at 40 bits and 3.4× at 51 bits.The authors describe this as a high-variance, exploitation-heavy search in which some MA runs descend deeply while others become trapped in local minima.Source: §6.2 · p. 10

6.3 Verification of the Supersingular Curve Found

  • The sole MA success was at 46 bits: NMD 0 at generation 24 after 1,613 evaluations, with point counting and an independent SageMath test confirming supersingularity.The discovered j-invariant has no small-discriminant CM structure and is specific to the prime.Source: §6.3 · pp. 10–11

6.4 Near-Supersingular Curves at 40 and 51 Bits

  • At 40 and 51 bits, the best MA curves remained ordinary, with NMD 19 and 3 and group orders only 19 and 3 points from p+1, respectively.The reported Hasse interval widths are approximately 1.5 × 10^6 and 6.7 × 10^7, respectively.Source: Table 6 · p. 11, §6.4 · p. 11
  • In the best 40- and 51-bit runs, most descent occurred in the first one or two generations; local search reached the 40-bit final values, while the 51-bit run reached its final value at generation 2.The population then stagnated for the remaining generations.Source: Table 7 · p. 12, §6.4 · p. 12

7 Discussion

The discussion characterizes the NMD landscape as globally informative but locally rugged, and interprets the ordinary curves found near trace zero as objects of independent interest. It also connects the 46-bit supersingular curve to oriented protocols while emphasizing that the tested prime sizes are computational benchmarks, not production parameters.

7.1 The NMD Landscape over Fp

  • The NMD landscape is globally informative but locally rugged: wide-radius mutations quickly find low-NMD curves, while adjacent j-invariants have essentially independent traces.Small mutations and integer-neighborhood local search therefore have no reliable gradient to follow.Source: §7.1 · p. 12
  • The memetic algorithm reaches much lower best-of-30 NMD values than random search at 46 and 51 bits, but population collapse leaves most runs stagnating in shrinking neighborhoods.The authors identify restart or niching mechanisms as possible ways to restore diversity.Source: §7.1 · pp. 12–13

7.2 Near-Supersingular Ordinary Curves

  • At 40 and 51 bits, the best NMD values of 19 and 3 correspond to relative trace deviations of 1.3×10^-5 and 4.5×10^-8 of the Hasse width.Across all 90 memetic-algorithm runs, the search produced a curve with |t| ≤ 6×10^4 at roughly 1.2×10^4 point counts per run.Source: §7.2 · p. 13
  • Curves with trace much smaller than 2√p have group orders close to p + 1 and can serve as test objects for isogeny-graph and endomorphism-ring computations.The authors propose further study of their density and endomorphism-ring structure, and of adapting NMD to target prescribed nonzero traces.Source: §7.2 · p. 13

7.3 Implications for Modern Oriented Isogeny Cryptography

  • The 46-bit non-CM Fp-rational supersingular curve has the canonical orientation Z[π] ≅ Z[√−p], while the tested 40-, 46-, and 51-bit primes are not production-scale security parameters.The paper frames these small primes as computational benchmarks and the results as proof of principle, not a deployment-ready key-generation engine.Source: §7.3 · p. 14

8 Conclusion and Future Work

The paper adapts an existing NMD-based search formulation to a one-dimensional prime-field search and evaluates it at three prime sizes. It finds an independently verified supersingular curve at 46 bits and near-zero-trace ordinary curves at the other scales, while identifying future work on diversity and scaling.

8 Conclusion and Future Work

  • The method retains the NMD objective while redesigning the chromosome, recombination, mutation schedule, and local search for a one-dimensional Fp search space.The formulation builds on Mart´ınez-D´ıaz et al..Source: §8 · p. 14
  • Across 30 seeds at each of three prime sizes, the memetic algorithm found an independently verified non-CM supersingular curve at 46 bits and ordinary curves with traces −19 and 3 at 40 and 51 bits.The latter traces are within 1.3×10^-5 and 4.5×10^-8 of the Hasse width from exact supersingularity.Source: §8 · p. 14
  • Future work includes adding restart or diversity mechanisms, using isogeny classes to diversify populations, characterizing near-supersingular curves, and testing larger primes.The authors also propose adapting NMD to target prescribed small nonzero traces and measuring success rates at 46 and 51 bits.Source: §8 · p. 14
  • The SageMath implementation, raw per-seed results, and execution logs are available from the author upon request.Source: Code and Data Availability · p. 15
Loading 2609.03249v1…