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

Memetic Search for Supersingular Elliptic Curves over Fp Ismel Martı́nez-Dı́az1 [0000-0002-7064-232X]

arXiv:2609.03249v1 [cs.CR] 3 Sep 2026

Department of Mathematics, Universitat de Lleida, C/ Jaume II, 69, 25001 Lleida, Spain imd6@alumnes.udl.cat

Abstract. The search for supersingular elliptic curves is a fundamental computational problem in isogeny-based cryptography. A recent metaheuristic formulation over Fp2 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 ≈ 1013 candidates. This work investigates metaheuristic search over the prime field Fp , the setting for oriented isogeny protocols such as CSIDH, OSIDH, and SQISign. Although the candidate space decreases from p2 to √ p, the supersingular locus is asymptotically sparse (O( p log p) curves), keeping the search exponentially difficult. We formulate a memetic algorithm tailored to Fp 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 ≈ 1.13 × 1015 ) 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 × 10−5 and 4.5 × 10−8 across the Hasse interval. These results demonstrate that NMD-driven memetic search effectively navigates the sparse Fp landscape and systematically locates near-supersingular structures. Keywords: Supersingular elliptic curves · Memetic algorithms · Metaheuristic optimization · Frobenius trace · Near-supersingular curves · Oriented isogeny cryptography

1

Introduction

Supersingular elliptic curves sit at the intersection of classical number theory and modern post-quantum cryptography. This section traces the historical path that made them central to isogeny-based protocols, reviews the computational challenge of generating them, explains why the present work moves the metaheuristic search from Fp2 to the prime field Fp , and summarizes our contributions and the organization of the paper.

2

1.1

I. Martı́nez-Dı́az

Historical Context and the Post-Quantum Paradigm

Elliptic curves have served as foundational building blocks of modern public-key cryptography since their independent introduction by Miller [17] and Koblitz [14] in the mid-1980s. For decades, classical elliptic curve cryptography (ECC) has relied on the intractability of the Elliptic Curve Discrete Logarithm Problem (ECDLP) in the group of rational points E(Fq ), supported by efficient pointcounting algorithms pioneered by Schoof [20] and subsequent Elkies-Atkin improvements. Pairing-based cryptography later expanded this domain through the Weil and Tate pairings on supersingular and pairing-friendly curves [2, 11]. However, the advent of quantum computation poses an existential threat to classical public-key systems: Shor’s algorithm [21] solves both integer factorization and discrete logarithms in polynomial time, rendering traditional RSA, Diffie-Hellman, and ECDLP-based schemes vulnerable. In response, postquantum cryptography (PQC) has emerged to design cryptosystems resistant to quantum cryptanalysis. Among post-quantum candidates, isogeny-based cryptography offers an appealing framework characterized by compact key sizes and rich underlying algebraic structures. The foundational ideas trace back to Couveignes’ hard homogeneous spaces [7] and Rostovtsev and Stolbunov’s public-key schemes [19], which used group actions on ordinary elliptic curves. The field shifted dramatically when Jao and De Feo [13] introduced the Supersingular Isogeny Diffie-Hellman (SIDH) protocol, transitioning from ordinary curves to supersingular curves defined over Fp2 to exploit the non-commutative structure and optimal Ramanujan expansion properties of supersingular isogeny graphs. In 2022, devastating polynomial-time attacks utilizing auxiliary torsion-point information, discovered by Castryck and Decru [5] and Maino and Martindale [15], broke SIDH and its standardized variant SIKE. Crucially, these attacks specifically exploited the auxiliary point evaluations shared during SIDH key exchange, leaving the fundamental problem of computing isogenies between supersingular curves uncompromised. Consequently, modern post-quantum research has pivoted toward new paradigms that avoid auxiliary point disclosure. Chief among these are: 1. Group-action protocols over prime fields: Commutative isogeny schemes such as CSIDH [4], OSIDH [6], and SCALLOP [9], which operate directly on the set of Fp -rational supersingular elliptic curves under the action of the ideal class group cl(O). 2. Oriented supersingular curves and signatures: Modern constructions such as SQISign [8] and general oriented isogeny protocols [1], which rely on curves equipped with explicit subring embeddings (orientations) in their endomorphism rings. In both settings, supersingular elliptic curves defined over the prime field Fp occupy a central role.

Memetic Search for Supersingular Curves over Fp

1.2

3

The Challenge of Supersingular Curve Generation

Constructing supersingular elliptic curves is therefore a core problem with immediate cryptographic utility. Deterministic methods exist: Bröker [3] proposed a polynomial-time algorithm using class field theory and complex multiplication (CM), and Sutherland [22] developed Hilbert class polynomial and modular polynomial techniques. However, deterministic CM constructions require computing class polynomials whose degrees grow with the class number h(−D), necessitating significant algebraic machinery. Treating curve discovery as an optimization problem offers an alternative metaheuristic approach. Martı́nez-Dı́az et al. [16] recently formulated the search for supersingular curves over Fp2 as a combinatorial optimization task. They introduced the NonMultiplicity Distance (NMD) as an objective function based on the Frobenius trace and demonstrated that evolutionary and local search heuristics could exploit the resulting fitness landscape. However, their empirical findings revealed a clear scalability threshold: once the candidate space exceeded approximately 1013 curves, naive random search became ineffective, and metaheuristic exploration encountered severe stagnation. The same study also observed that the NMD objective tends to drive the search towards ordinary curves whose Frobenius trace is very close to zero, and suggested that such “near-supersingular” curves deserve study in their own right. 1.3

Motivation and Shift to the Prime Field Fp

The present work reformulates the metaheuristic search from Fp2 to the prime field Fp . Why shift the search space? – Combinatorial Challenge vs. Search Complexity: Over Fp2 , the total space of j-invariants is p2 , and there are ≈ p/12 supersingular j-invariants, yielding a density of ≈ 1/(12p). Over Fp , the total candidate space is reduced to p. However, the number of supersingular j-invariants in Fp is only √ √ O( p log p) [10]. The resulting hit probability O(log p/ p) remains exponentially small in log p. Thus, for cryptographically relevant primes (p ≥ 1013 ), finding a supersingular curve in Fp remains a formidable needle-in-a-haystack problem where uninformed search inevitably fails. – A One-Dimensional Search Space: Over Fp the chromosome is a single field element j ∈ Fp , which admits natural integer-arithmetic neighborhoods, bit-level recombination, and a direct, unambiguous notion of “distance” on which mutation radii and local search can be scheduled. This removes the extension-field representation overhead of the Fp2 formulation. – Direct Applicability to Oriented Protocols: Fp -rational supersingular curves naturally possess an orientation by the imaginary quadratic order √ Z[π] ∼ = Z[ −p] given by the Frobenius endomorphism π. Finding curves directly in Fp yields the precise starting curves required by modern oriented protocols (CSIDH, OSIDH, SCALLOP, and oriented signature schemes), which cannot directly utilize general Fp2 supersingular curves.

4

1.4

I. Martı́nez-Dı́az

Contributions and Paper Organization

This paper makes the following main contributions: 1. Formulation of Fp Memetic Search: We adapt the combinatorial optimization model of Martı́nez-Dı́az et al. [16] to the prime field Fp , designing a one-dimensional chromosome representation, bit-level crossover operators, adaptive mutation radius schedules, and local search routines, while keeping the NMD objective function unchanged. 2. Experimental Validation up to 1015 Scale: We evaluate random search and the memetic algorithm on three primes of increasing size – 40-bit, 46-bit, and a 51-bit challenge prime (p ≈ 1.13 × 1015 ) – over 30 independent seeds per configuration. The memetic algorithm reaches an exact, independently verified supersingular curve at the 46-bit benchmark, and at the other two scales converges to ordinary curves with Frobenius trace |t| = 19 and |t| = 3, respectively. 3. Near-Supersingular Ordinary Curves: We quantify how close the memetic search gets to supersingularity relative to the Hasse interval, show that this behavior is systematic rather than accidental, and argue – reinforcing the observation of Martı́nez-Dı́az et al. [16] – that NMD-driven search over Fp is an efficient generator of near-supersingular curves worthy of independent study. The remainder of this paper is organized as follows: Section 2 provides mathematical background on supersingular curves and memetic algorithms. Section 3 analyzes the search spaces and problem formulation. Section 4 describes the NMD objective function. Section 5 details the proposed memetic algorithm. Section 6 presents the experimental setup and empirical results. Section 7 discusses implications, and Section 8 concludes with future research directions.

2

Background and Preliminaries

This section collects the mathematical and algorithmic notions on which the rest of the paper depends. We first recall elliptic curves over prime fields and the role of the Frobenius trace in characterizing supersingularity, and then summarize the memetic algorithm paradigm that drives our search. 2.1

Elliptic Curves and the Frobenius Trace

Let p > 3 be prime, and let Fp denote the finite field of p elements. An elliptic curve E defined over Fp can be described by the short Weierstrass equation: E/Fp :

y 2 = x3 + Ax + B,

A, B ∈ Fp ,

with non-zero discriminant ∆ = −16(4A3 + 27B 2 ) ̸= 0.

(1)

Memetic Search for Supersingular Curves over Fp

5

The j-invariant of E, given by j(E) = 1728

4A3 , 4A3 + 27B 2

(2)

classifies E up to isomorphism over the algebraic closure Fp . For any j ∈ Fp \ {0, 1728}, a canonical curve representative having j(Ej ) = j is given by: Ej :

y 2 = x3 +

3j 2j x+ . 1728 − j 1728 − j

(3)

The boundary cases j = 0 and j = 1728 correspond respectively to curves of the form y 2 = x3 + B and y 2 = x3 + Ax. The p-power Frobenius endomorphism π : E → E is defined by π(x, y) = (xp , y p ). The number of Fp -rational points is governed by Hasse’s theorem: #E(Fp ) = p + 1 − t,

(4) √

where the Frobenius trace t ∈ Z satisfies the Hasse bound |t| ≤ 2 p. Definition 1 (Supersingularity). An elliptic curve E/Fp is supersingular √ if and only if t ≡ 0 (mod p). For primes p > 3, the Hasse bound |t| ≤ 2 p < p implies that E/Fp is supersingular if and only if: t=0

⇐⇒

#E(Fp ) = p + 1.

(5)

For supersingular curves, the full endomorphism ring End(E) over Fp is a maximal order in a definite quaternion algebra Bp,∞ ramified at p and ∞ [12]. In contrast, p for ordinary curves, End(E) is an order in the imaginary quadratic field Q( t2 − 4p). Over the base field Fp , the Fp -rational endomorphism ring of √ a supersingular curve is an order in Q( −p). 2.2

Memetic Algorithms

Memetic Algorithms (MAs) [18] are population-based metaheuristics that synergistically combine global evolutionary exploration with problem-specific local refinement (local search / meme exploitation). The evolutionary operators (selection, recombination, and mutation) preserve population diversity across the global search space, while local search intensifies exploitation around promising candidate regions. In combinatorial and arithmetic domains where the objective function presents complex, non-linear, or deceptive landscapes, memetic algorithms frequently outperform pure genetic algorithms and random sampling by avoiding premature convergence and navigating rugged fitness basins [23].

3

Search Space and Problem Formulation

Before describing the algorithm, we make precise the combinatorial object being searched. This section contrasts the Fp2 search space of previous work with the Fp space adopted here, quantifies the density of supersingular j-invariants in each, and motivates the concrete prime sizes used as experimental benchmarks.

6

I. Martı́nez-Dı́az

3.1

Comparison: Search over Fp2 vs. Fp

The choice of search domain fundamentally determines the combinatorial and arithmetic characteristics of the optimization problem. Table 1 summarizes the key differences between searching over Fp2 (the setting of Martı́nez-Dı́az et al. [16]) and over Fp (the present work). Table 1. Comparison of the search spaces and density characteristics. Field

Space Size 2

Fp2

p

Fp

p

Supersingular Count

Density

≈ p/12 √ O( p log p)

1 ≈ 12p   p √ O log p

Random Hit Scale

O

O(p)  √  p log p

Over Fp2 , the candidate space has size p2 , and the number of supersingular j-invariants is ⌊p/12⌋ + ε (where ε ∈ {0, 1, 2}). Over Fp , the candidate space is p, and the number of Fp -rational supersingular j-invariants is bounded by √ O( p log p) as established by Delfs and Galbraith [10]. Restricting the search to Fp offers two structural advantages: 1. Dimensionality reduction: The optimization space is one-dimensional (j ∈ Fp ), eliminating complex extension-field representation overhead and giving mutation and local search a natural integer metric to operate on. 2. Cryptographic alignment with oriented protocols: Modern oriented isogeny schemes (CSIDH [4], OSIDH [6], SCALLOP [9]) explicitly require Fp -rational supersingular curves as public starting curves to instantiate the √ class group action cl(Z[ −p]) ⋆ E. Despite the higher relative density in Fp compared to Fp2 , the probability √ O(log p/ p) remains vanishingly small for large primes: for a 46-bit prime (p ≈ 3.5 × 1013 ), the density is on the order of 10−6 , meaning uninformed random search requires millions of point counts and, within feasible evaluation budgets, succeeds only by chance. 3.2

Experimental Benchmark Selection

Martı́nez-Dı́az et al. [16] observed that naive random search stagnated when the search space exceeded approximately 1013 candidates (243 ≲ N ≲ 247 ). For our Fp formulation, the candidate cardinality is N = p. Following the same escalating validation strategy used by Martı́nez-Dı́az et al. to probe scalability, we add a third, more challenging prime beyond their 1013 –1014 regime. We adopt a three-stage benchmarking methodology: The 46-bit prime places our search space directly into the 3.52 × 1013 candidate scale used as the primary benchmark, while the 51-bit prime (p ≈ 1.13 × 1015 , about 32× larger) tests how the memetic search degrades well beyond

Memetic Search for Supersingular Curves over Fp

7

Table 2. Selected prime parameters for the experimental study. Stage Calibration Benchmark Ext. Challenge

Bits 40 46 51

Prime p

Space |Sp |

Purpose

11

549,755,813,927 5.50 × 10 Calibration & baseline 35,184,372,088,907 3.52 × 1013 1013 -scale benchmark 1,125,899,906,842,679 1.13 × 1015 Beyond-1013 scaling

the regime originally identified as problematic. All three primes satisfy p ≡ 3 (mod 4), so that y 2 = x3 + x (j = 1728) is supersingular and the boundary case is handled uniformly by the implementation.

4

Objective Function

We retain the NonMultiplicity Distance (NMD) objective function introduced by Martı́nez-Dı́az et al. [16] without modification, ensuring that the optimization target is preserved while changing the search space. For an elliptic curve E/Fp , let t = p + 1 − #E(Fp ) be its Frobenius trace. The NonMultiplicity Distance is defined as:   NMD(E) = min t mod p, p − (t mod p) . (6) The minimization problem is formulated as: min f (j) = NMD(Ej )

j∈Fp

where Ej is the canonical curve representative defined in (3), satisfying: jpk 0 ≤ f (j) ≤ . 2

(7)

(8)

A fitness value f (j) = 0 indicates that t ≡ 0 (mod p). For primes p > 3, this is both necessary and sufficient for Ej to be supersingular. √ Because |t| ≤ 2 p < p/2 for all p > 16, the NMD of any curve over Fp is simply |t|. The objective is therefore a direct measure of the absolute Frobenius √ trace, and its natural scale is the width 2 p of the Hasse interval rather than p itself. We use this observation in Section 6 to interpret non-zero NMD values.

5

Proposed Memetic Approach

The proposed method is a memetic algorithm whose population lives directly in Fp . We describe the one-dimensional chromosome encoding and its evaluation via point counting, followed by the evolutionary operators – bit-wise recombination, adaptive mutation, and periodic local search – that have been adapted to this finite-field representation.

8

5.1

I. Martı́nez-Dı́az

Chromosome Representation and Evaluation

An individual chromosome is encoded as a single field element: χ = j ∈ {0, 1, . . . , p − 1}.

(9)

Evaluating an individual consists of constructing the canonical curve Ej via (3), computing the curve order #Ej (Fp ) via SEA/point-counting, determining the trace t, and evaluating f (j) = NMD(Ej ). The initial population is sampled uniformly at random from Fp without repetition. 5.2

Evolutionary Operators

Bit-Wise Recombination (Crossover). Given two parent chromosomes j1 , j2 ∈ Fp , we represent them in binary form: j1 =

n−1 X k=0

k

b1,k 2 ,

j2 =

n−1 X

b2,k 2k ,

n = ⌈log2 p⌉.

(10)

k=0

A bit interval [κ1 , κ2 ] is chosen uniformly at random, and bits within the interval are swapped between parents. The resulting integer is reduced modulo p. This enables recombination over single finite field elements. Adaptive Neighborhood Mutation. For an individual j, mutation produces an offspring: j ′ = (j + δ) mod p, δ ∈R [−rg , rg ], (11) where the mutation radius rg decays linearly across generations g ∈ {0, . . . , Gmax − 1}:   g g rg = rinit 1 − + rfinal . (12) Gmax − 1 Gmax − 1 This schedule begins with broad global exploration (rinit = ⌊p/4⌋) and anneals toward fine-grained local refinement (rfinal = ⌊p/216 ⌋). Selection and Elitism. Parents are chosen by tournament selection of size three. The best Nelite individuals of each generation are carried over unchanged. Local Search Exploitation. Periodically (every 10 generations), an intensification phase is triggered on the elite individuals. For an elite candidate j, local search explores an integer neighborhood Nρ (j) = {(j + k) mod p : −ρ ≤ k ≤ ρ} with a radius ρ that is halved after each round of unsuccessful attempts, greedily accepting improvements f (j ′ ) < f (j).

Memetic Search for Supersingular Curves over Fp

6

9

Experimental Evaluation and Results

We now evaluate uniform random sampling and the memetic algorithm on the primes of Table 2. After fixing the experimental configuration, we compare success rates and best fitness across all configurations, independently verify the supersingular curve found, and examine the convergence behavior of the memetic search and the near-supersingular curves it returns. 6.1

Experimental Configuration

All algorithms were implemented and evaluated in SageMath 10.x. Experiments were executed across 30 independent random seeds per configuration – a standard sample size for statistically meaningful success-rate estimates – for each of the three primes in Table 2: – Random: Uniform random sampling over Fp (10,000 evaluations/run). – MA: The memetic algorithm of Section 5 over Fp . Table 3 lists the algorithmic parameter configuration. With a population of 32 and 200 generations plus periodic local search, a full MA run consumes approximately 11,780 curve evaluations, i.e. a budget comparable to (slightly above) the 10,000 evaluations of the random baseline. Table 3. Memetic algorithm parameter configuration. Parameter

Value

Population size (Npop ) 32 Maximum generations (Gmax ) 200 Crossover probability (pc ) 0.70 Mutation probability (pm ) 0.60 Initial mutation radius (rinit ) ⌊p/4⌋ Final mutation radius (rfinal ) ⌊p/216 ⌋ Tournament size 3 Elite count (Nelite ) 4 Local search frequency Every 10 generations Local search initial radius (ρinit ) 214 Local search final radius (ρfinal ) 24 Number of independent seeds 30

6.2

Empirical Comparison and Success Rates

Table 4 presents the comparative experimental results for the two search methods at the three tested prime sizes, over 30 independent seeds per configuration (180 runs in total).

10

I. Martı́nez-Dı́az

Table 4. Performance comparison across 30 independent runs per configuration (primes as in Table 2). “Best” is the minimum NMD over all 30 runs; “Mean” and “Median” are taken over the per-run best NMD. Prime Method Runs Success Best NMD Mean Median 40 bits Random MA

30 30

1/30 0/30

0 19

105.6 367.5

68.0 256.0

46 bits Random MA

30 30

0/30 1/30

80 0

1,033.8 768.5 2,758.7 1,968.0

51 bits Random MA

30 30

0/30 0/30

310 3

3,753.2 2,752.5 12,740.5 8,742.0

Two complementary patterns emerge. First, in terms of the best curve found over 30 seeds, the memetic algorithm consistently reaches values far below random search at the two larger primes: NMD 0 versus 80 at 46 bits and NMD 3 versus 310 at 51 bits. At 40 bits random search hit an exact supersingular curve once (j = 535,482,084,752, seed 15, after 995 evaluations) – a chance event con√ sistent with the O(log p/ p) density at this small prime – while the best MA run reached NMD 19. Second, in terms of the mean and median per-run best NMD, random search is better than MA at all three primes. This is the signature of a high-variance, exploitation-heavy search: MA runs that find a promising basin descend into it very deeply, but runs that do not are trapped in local minima of the NMD landscape and end far from the target, whereas 10,000 uniform samples give a stable, moderately good minimum. The gap widens with p (the MA mean is 3.5× the random mean at 40 bits and 3.4× at 51 bits), which is the expected behavior for a fixed evaluation budget on an exponentially growing space. Section 7 returns to this trade-off. 6.3

Verification of the Supersingular Curve Found

The single MA success occurred at the 46-bit benchmark p = 35,184,372,088,907 (seed 23), reaching NMD = 0 at generation 24 after 1,613 curve evaluations. The algorithm returned j = 3,292,287,772,342, (13) whose canonical curve (3) is E:

y 2 = x3 + 1,981,898,072,918 x + 13,049,389,411,581

(mod p).

(14)

NMD(E) = 0,

(15)

Direct point counting gives #E(Fp ) = 35,184,372,088,908 = p + 1 =⇒ t = 0,

and SageMath’s independent is supersingular() test confirms that E is supersingular. Unlike the classical CM curves with j ∈ {0, 1728}, this j-invariant

Memetic Search for Supersingular Curves over Fp

11

has no small-discriminant CM structure and is specific to the prime p; it was located purely by the NMD-driven search. Table 5 shows the best-fitness trajectory of this run. The population drops from an initial best of 7,494 to 3,355 in one generation and then, after a plateau, local search at generation 24 closes the remaining gap to zero. Table 5. Convergence of MA for p = 35,184,372,088,907 (seed 23). Only generations at which the best NMD improved are shown.

6.4

Generation

Best NMD

0 1 24

7,494 3,355 0 (supersingular curve found)

Near-Supersingular Curves at 40 and 51 Bits

At the other two primes the memetic algorithm did not reach NMD = 0 in any run, but its best curves are remarkably close. Table 6 lists the best MA curve at √ each scale together with its Frobenius trace and the relative deviation |t|/(2 p) from exact supersingularity, measured against the width of the Hasse interval. Table 6. Best memetic-search curve at each prime, with Frobenius trace and relative deviation from supersingularity. Bits j-invariant

Seed

40 46 51

1 23 18

97,044,492,992 3,292,287,772,342 527,221,685,817,413

#E(Fp )

t

√ |t|/2 p

549,755,813,947 −19 1.3 × 10−5 35,184,372,088,908 0 0 1,125,899,906,842,677 3 4.5 × 10−8

The 40-bit curve E:

y 2 = x3 + 197,917,316,633 x + 315,196,815,731

(mod 549,755,813,927) (16) has #E(Fp ) = p + 20, i.e. t = −19, and the 51-bit curve E:

y 2 = x3 + 139,804,163,754,131 x + 468,502,744,783,647

(mod 1,125,899,906,842,679)

(17)

has #E(Fp ) = p − 2, i.e. t = 3. Both are ordinary curves, but their group orders differ from the supersingular value p + 1 by only 19 and 3 points respectively, out of a Hasse interval of width ≈ 1.5 × 106 and ≈ 6.7 × 107 .

12

I. Martı́nez-Dı́az

Table 7 shows how these two runs converged. In both cases the bulk of the descent happens in the first one or two generations – driven by the wide initial mutation radius – and the final small values are reached either by local search (40 bits, generation 63 and 99) or already at generation 2 (51 bits), after which the population stagnates for the remaining generations. Table 7. Convergence of the best MA runs at 40 bits (seed 1) and 51 bits (seed 18). Only generations at which the best NMD improved are shown. 40 bits Gen. Best NMD 0 1 27 53 63 99

7

36,913 3,224 2,177 1,839 63 19

51 bits Gen. Best NMD 0 1 2

2,485,014 54,654 3

Discussion

The results of Section 6 raise three questions: what the NMD landscape looks like from the point of view of the memetic operators, what can be learned from the near-supersingular ordinary curves that the search returns, and what these findings mean for cryptographic practice. We address each in turn, and close with an explicit statement of the scope and limitations of the parameter sizes studied here. 7.1

The NMD Landscape over Fp

Since NMD(Ej ) = |t(Ej )| over Fp , the objective is the absolute value of a quantity that, for j ranging over Fp , is distributed approximately according to the √ √ Sato–Tate law on [−2 p, 2 p]. Two consequences follow. First, the landscape is √ globally informative: a uniformly random j has expected NMD of order p, so √ any curve with NMD ≪ p is a genuine signal, and the wide-radius mutations of the early generations act as a stratified sampler that quickly finds such curves (the drop from ∼ 104 –106 to ∼ 103 –104 in the first generation of every trace in Section 6). Second, the landscape is locally rugged : adjacent j-invariants j and j + 1 have essentially independent traces, so there is no gradient that small mutations or the integer neighborhoods of local search can follow reliably. The trace of a curve is an arithmetic function of j, not a smooth one. This explains the pattern of Table 4. The memetic algorithm excels at the first phase – its best-of-30 NMD is far below that of random search at 46 and 51

Memetic Search for Supersingular Curves over Fp

13

bits – but once the population has collapsed onto a few low-NMD individuals, the remaining operators are effectively performing a random search in a shrinking neighborhood, and most runs stagnate. The higher mean best NMD of MA relative to random sampling is the cost of that premature convergence: the 30 random runs each enjoy 10,000 independent draws, whereas an MA run spends most of its ≈ 11,780 evaluations near a handful of attractors. An obvious remedy, which we leave for future work, is a restart or niching mechanism that re-injects diversity when the population stagnates. 7.2

Near-Supersingular Ordinary Curves

Although exact supersingularity was reached only once, the curves returned by the memetic search are extremely close to it when measured on the natural scale of the problem. At 51 bits, the best NMD of 3 corresponds to a relative trace deviation of 4.5 × 10−8 of the Hasse width; at 40 bits, the best NMD of 19 corresponds to 1.3 × 10−5 . Even the mean best NMD over all 30 seeds at 51 bits (≈ 1.27 × 104 ) is only about 1.9 × 10−4 of the Hasse interval. In other words, the memetic algorithm systematically converges to ordinary curves whose Frobenius trace is vanishingly small relative to the range of admissible traces, even though it rarely lands on the exact zero. Martı́nez-Dı́az et al. [16] already observed this phenomenon in their seminal formulation over Fp2 and argued that ordinary curves with near-zero trace are themselves of independent interest. Our Fp experiments strongly reinforce √ that view, and make it quantitative. Curves with |t| ≪ 2 p have group orders #E(Fp ) = pp + 1 − t extremely close to p + 1 and endomorphism rings that are orders in Q( t2 − 4p), a field of discriminant very close to −4p; for the 51-bit curve of Table 6, t2 − 4p = 9 − 4p. Such curves share many arithmetic features with the supersingular case (in particular the structure of the ℓ-torsion for small ℓ | #E(Fp ) and the geometry of their isogeny classes) while remaining ordinary, which makes them natural test objects for isogeny-graph and endomorphismring computations and potential ingredients for the S-box and cycle-generation applications explored in [16]. We therefore regard the systematic study of such “near-supersingular” ordinary curves – their density, their endomorphism-ring structure, and whether the NMD objective can be adapted to target a prescribed small trace t ̸= 0 – as a worthwhile research direction, and note that the memetic search over Fp is already an efficient generator of them: every one of the 90 MA runs in this study produced a curve with |t| ≤ 6 × 104 at a cost of roughly 1.2 × 104 point counts. 7.3

Implications for Modern Oriented Isogeny Cryptography

The transition from Fp2 to Fp is conceptually relevant to the post-SIDH cryptographic landscape. Protocols such as CSIDH [4], OSIDH [6], SCALLOP [9], and oriented signatures [1, 8] require starting curves with well-understood endomorphism subrings. An Fp -rational supersingular curve comes equipped with

14

I. Martı́nez-Dı́az

√ a canonical orientation by Z[π] ∼ = Z[ −p]. The 46-bit curve of Section 6.3 is a non-CM Fp -rational supersingular curve of exactly this kind, located by a generic optimization procedure rather than by a CM or isogeny-walk construction. Remark 1 (Cryptographic Security and Parameter Scale Limitation). We explicitly emphasize that the prime sizes evaluated in this work (40-bit, 46-bit, and 51-bit, up to p ≈ 1.13 × 1015 ) serve strictly as computational benchmarks to study optimization dynamics and fitness landscapes at the 1013 –1015 candidate scale. These small primes are not representative of production parameter sizes and cannot be used for post-quantum security. Practical post-quantum isogeny systems require primes of cryptographically relevant bit lengths (e.g., p ≈ 2512 for CSIDH-512, or p ≥ 2256 for standard classical and quantum security margins), where point counting via Schoof’s algorithm remains tractable but exhaustive enumeration is physically impossible. The present results should therefore be interpreted as a proof-of-principle study of metaheuristic search over Fp , rather than as a deployment-ready key-generation engine for post-quantum schemes.

8

Conclusion and Future Work

This paper presented a memetic algorithm for the search of supersingular elliptic curves over the prime field Fp , building on the optimization formulation of Martı́nez-Dı́az et al. [16]. The NMD objective was retained unchanged, while the chromosome representation, recombination, mutation schedule, and local search were redesigned for a one-dimensional finite-field search space. Empirical benchmarks over 30 independent seeds at three primes – 40-bit, 46-bit, and a 51-bit challenge prime (p ≈ 1.13 × 1015 ) – showed that the memetic algorithm locates an exact, independently verified, non-CM supersingular curve at the 46-bit benchmark (j = 3,292,287,772,342), and at the other two scales converges to ordinary curves with Frobenius traces t = −19 and t = 3, i.e. within 1.3 × 10−5 and 4.5 × 10−8 of the Hasse width from exact supersingularity. The comparison with uniform random sampling revealed a clear trade-off: the memetic search reaches much deeper minima in its best runs but exhibits higher variance and premature convergence on average. Promising avenues for future work include: 1. Adding restart, niching, or diversity-preservation mechanisms to counter the premature convergence observed in the majority of MA runs, and measuring the resulting success rate at 46 and 51 bits; 2. Exploiting the isogeny class of a near-supersingular curve: all curves ℓisogenous to E share its trace, so the isogeny graph could be used to enlarge or diversify the population without additional point counting; 3. Characterizing the near-supersingular ordinary curves returned by the search (Section 7.2), following the direction suggested by Martı́nez-Dı́az et al. [16], and adapting the NMD objective to target prescribed small traces t ̸= 0; 4. Scaling the experimental campaign towards larger primes to determine how the best-run NMD grows with log p under a fixed evaluation budget.

Memetic Search for Supersingular Curves over Fp

15

Code and Data Availability. The SageMath implementation used for all experiments, together with the raw per-seed results and execution logs, is available from the author upon request. Disclosure of Interests. The author has no competing interests to declare that are relevant to the content of this article.

References 1. Arpin, S., Clements, J., Dartois, P., Eriksen, J.K., Kutas, P., Wesolowski, B.: Finding orientations of supersingular elliptic curves and quaternion orders. Designs, Codes and Cryptography 92, 3447–3493 (2024). 2. Boneh, D., Franklin, M.: Identity-based encryption from the Weil pairing. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 213–229. Springer (2001). 3. Bröker, R.: Constructing supersingular elliptic curves. Journal of Combinatorics and Number Theory 1(3), 269–273 (2009). 4. Castryck, W., Lange, T., Martindale, C., Panny, L., Renes, J.: CSIDH: An efficient post-quantum commutative group action. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11274, pp. 395–427. Springer (2018). 5. Castryck, W., Decru, T.: An efficient key recovery attack on SIDH. In: Handschuh, H., Lysyanskaya, A. (eds.) EUROCRYPT 2023. LNCS, vol. 14008, pp. 423–447. Springer (2023). 6. Colò, L., Kohel, D.: Orienting supersingular isogeny graphs. Journal of Mathematical Cryptology 14(1), 414–437 (2020). 7. Couveignes, J.M.: Hard homogeneous spaces. Cryptology ePrint Archive, Report 2006/291 (2006). 8. De Feo, L., Kohel, D., Leriche, A., Petit, C., Wesolowski, B.: SQISign: Compact post-quantum signatures from quaternions and isogenies. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 64–93. Springer (2020). 9. De Feo, L., Delpech de Saint Guilhem, T., Fouotsa, L., Kutas, P., Leriche, A., Petit, C., Silva, J., Wesolowski, B.: SCALLOP: Scaling CSIDH with sublinear order pairings. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, vol. 14004, pp. 67–98. Springer (2023). 10. Delfs, C., Galbraith, S.D.: Computing isogenies between supersingular elliptic curves over Fp . Designs, Codes and Cryptography 78(2), 425–440 (2016). 11. Galbraith, S.D.: Supersingular curves in cryptography. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 495–513. Springer (2001). 12. Galbraith, S.D.: Mathematics of Public Key Cryptography. Cambridge University Press (2012). 13. Jao, D., De Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. In: Yang, BY. (ed.) PQCrypto 2011. LNCS, vol. 7071, pp. 19–34. Springer (2011). 14. Koblitz, N.: Elliptic curve cryptosystems. Mathematics of Computation 48(177), 203–209 (1987). 15. Maino, L., Martindale, C.: An attack on SIDH with arbitrary starting curve. In: Handschuh, H., Lysyanskaya, A. (eds.) EUROCRYPT 2023. LNCS, vol. 14008, pp. 448–471. Springer (2023).

16

I. Martı́nez-Dı́az

16. Martı́nez-Dı́az, I., Ali, R., Jamil, M.K.: On the Search for Supersingular Elliptic Curves and Their Applications. Mathematics 13(2), 188 (2025). https://doi.org/10.3390/math13020188 17. Miller, V.S.: Use of elliptic curves in cryptography. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol. 218, pp. 417–426. Springer (1985). 18. Moscato, P.: On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech Concurrent Computation Program, Technical Report 826 (1989). 19. Rostovtsev, A., Stolbunov, A.: Public-key cryptosystem based on isogenies. Cryptology ePrint Archive, Report 2006/145 (2006). 20. Schoof, R.: Elliptic curves over finite fields and the computation of square roots mod p. Mathematics of Computation 44(170), 483–494 (1985). 21. Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 124–134. IEEE (1994). 22. Sutherland, A.V.: Identifying supersingular elliptic curves. LMS Journal of Computation and Mathematics 15, 317–325 (2012). 23. Wolpert, D.H., Macready, W.G.: No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation 1(1), 67–82 (1997).

Related documents

• Ordinary 3-Isogeny Graphs and Improvement of Supersingularity Testing for Twisted Hessian Curves over Prime Fields#998602
• The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally#1036404
• The Supersingular Isogeny Problem in Time and Memory $p^{1/3+o(1)}$, Unconditionally#1006778
• Algebraic Modelings of the Supersingular Isogeny Problem#343362
• Search for squarks and gluinos in events with hadronically decaying tau leptons, jets and missing transverse momentum in proton–proton collisions at s=13 TeV recorded with the ATLAS detector#814607