title	subtitle	author	keywords
Selection of libsecp256k1 compatible elliptic curves	A complete enumeration and ranking	HarryR	elliptic-curve secp256k1 glv eisenstein cryptography

\begin{abstract}

We present a complete analysis of elliptic curves suitable as drop-in replacements for secp256k1. The various optimizations used by libsecp256k1 constrain the search to primes within 31-bit ranges, enabling exhaustive enumeration. We narrow this space through successive filtering steps to yield approximately 7,000 prime-ordered curves. We define a security ideal and measure distance from this ideal across multiple dimensions to rank all candidates, providing rigidity through balanced consideration of multiple cryptographically desirable properties rather than arbitrary threshold selection. This distance-based approach naturally yields conservative choices rather than merely the first candidate meeting incremental search criteria. Statistical comparison of secp256k1, random samples, and our optimal selection validates this methodology. The same method extends to 255-bit primes, where the additional bit of headroom enables simplified point compression via a parity bit. As cryptographic sovereignty becomes increasingly important, the bar for transparency and rigor in standardization has risen substantially, breaking free of the computational limitations of 25 years ago.

\end{abstract}

---

::: columns

Introduction

The elliptic curve secp256k1 is remarkable for becoming one of the most widely deployed secure cryptographic primitives in use today and has withstood the test of time since its definition in 2000[@SEC2v1], but open questions remain about the standardization process &emdash; particularly regarding the relationship between parameter selection and presently unknown attacks. Meanwhile, computers and subsequent standards have evolved substantially: modern systems predominantly optimize for 64-bit architectures, and current research largely focuses on pairing-friendly curves or post-quantum alternatives, even as critical internet infrastructure continues to rely on choices made at the end of the last millennium.

This paper presents an open, deterministic, and reproducible approach for finding candidate Koblitz-style curves over generalized Mersenne primes that can serve as drop-in replacements for secp256k1. We present a single optimized 256-bit curve, with the methodology extending naturally to 255-bit primes where the additional bit of headroom allows a parity bit for point recovery.

Usage

First, checkout the repository from GitHub:

$ git clone github:HarryR/barbleglaster
$ cd barbleglaster

Whether you're reading the PDF version or the README.md file in the source code, this document can be typeset using Pandoc [@pandoc], and its graphs are produced by Sage [@sagemath] Python scripts using the data in the repository.

The data produced by this project is deterministic and reproducible; it consists of a multi-step pipeline, which will be detailed further in the Methodology section, that can be used to perform the same analysis on any chosen bit length. Smaller bit lengths can be used to verify the process quickly; at 200+ bits the process takes many days to compute. To get started, run:

$ make

Or use the lib_glv.py utility to analyze curves

# args are: 2^256 - 2^32 - 997, g^i = 243
$ python3 lib_glv.py 256 32 977 243

Alternative, to see the top 3, bottom 3 and any curves of interest (e.g. 256 977 is secp256k1), use:

$ python3 results.py 256

libsecp256k1 Optimizations

To remain compatible with existing libraries, any curve parameters we propose must have the same form and permit the same optimizations as libsecp256k1 [@libsecp256k1]. secp256k1 is a j-invariant 0 curve with the short Weierstraß form of

$$ E_p : y^2 = x^3 + b \mod{p} $$

For a prime field $\mathbb{F}_p$ where $p \equiv 3 \pmod{4}$ and $gcd(2,p-1)=2$, any quadratic residue in $\mathbb{F}_p$ has a square root, the root of $y^2$ can be derived via exponentation as follows, but the sign information is lost thus requiring an additional parity bit to correct the $y$ coordinate: $$\pm y = (x^3 + b)^{\frac{p+1}{4}}$$ Multiplication and exponentiation in large integer fields consists of many modulo reductions, as such the $L$ bit prime field $\mathbb{F}_p$ where $2^{L-1} < p \le 2^L$ is chosen to be close to computer word-size boundaries, this follows the SECG standards choice, with the additional constraint that libsecp256k1 requires the $b$ from the curve equation be a positive 31-bit integer:

$$ p \in {2^L - 2^{32} - c \mid c \in \mathbb{Z}^+, c < 2^{31}} $$ To increase the interval between reductions the field can be represented as $n$ limbs of $\ell$ bits each, stored in $r$-bit integers. This provides a headroom of $r-\ell$ bits per limb, allowing additions to accumulate a 'magnitude' which tracks how many operations can be performed before reduction becomes necessary, using the radix-$2^{51}$ trick [@radix-51-trick]: $$ \mathbb{F} = { \sum_{i=0}^{n-1} x_i \cdot 2^{i \cdot \ell} \space : \space x_i \in [0, 2^{\ell + \text{mag}(x)}] } $$

Efficient GLV Scalar Decomposition

The GLV [@GLV01] optimization leverages the endomorphism structure of j-invariant 0 curves. Let $\beta \in \mathbb{F}_p$ be an element of order 3, the map $\phi : E_p \to E_p$ defined by $(x,y) \mapsto (\beta x,y)$ and $\mathcal{O} \mapsto \mathcal{O}$ is an endomorphism defined over $\mathbb{F}_p$. If $G \in E_p$ is a point of prime order $q$, then $\phi$ acts on $\langle G \rangle$ as multiplication by $\lambda$, where $\lambda$ satisfies $\lambda^2 + \lambda + 1 \equiv 0 \pmod{q}$.

Decomposing scalars enable simultaneous computation using Shamir's trick, processing both scalar multiplications in parallel with precomputed combinations $(P, \phi(P), P+\phi(P))$. Computing $kG$ for random $k \in [1,q-1]$ can be optimized by decomposing $k = k_1 + k_2 \lambda \bmod{q}$ where $k_1,k_2 \in [0, \lceil \sqrt{q} \rceil]$, enabling: $$kP = k_1 P + k_2 \phi(P)$$

The critical optimization by Gouvêa et al. [@Gouvea2012] eliminates expensive multiple-precision division operations or LLL basis calculations. Instead of computing $\beta_1 = (kv_{21})/d$ and $\beta_2 = -(kv_{11})/d$ directly, precomputed constants are used: $$g_1 = \left\lfloor \frac{2^t v_{21}}{d} \right\rfloor, \quad g_2 = \left\lfloor \frac{2^t v_{11}}{d} \right\rfloor$$

where $t = \lceil \log_2 k \rceil + 2$. The decomposition then becomes:

beta_1 = floor((k*g_1)/2**t) = (k*g_1) >> t
beta_2 = -floor((k*g_2)/2**t) = -(k*g_2) >> t

Smith [@Smith2013] introduced an improve approach for constant-time implementation by examining the discarded bit during the right shift operation. If the $(t-1)$-th bit is 1, the coefficient is incremented, ensuring proper rounding without conditional branches that could leak timing information.

Security: Cheon Resistance and Factor Distribution

In 2006, Jung Hee Cheon demonstrated [@Cheon06] a specialized attack against cryptosystems relying on the Strong Diffie-Hellman (SDH) assumption. The attack exploits the factorization structure of group orders: given a positive divisor $d$ of $p-1$, the SDH problem can be solved in $O(\log p \cdot \sqrt{p/d} + \sqrt{d})$ group operations using $O(\max(\sqrt{p/d},\sqrt{d}))$ memory. This reduces complexity by $O(\sqrt{d})$ compared to generic discrete logarithm attacks, meaning security depends not just on the size of $p$, but on the factorization properties of $p \pm 1$ and $q \pm 1$.

The vulnerability is most pronounced with balanced factors: a 256-bit number with equal ~128-bit factors drops from 128-bit to ~64-bit security. However, very unbalanced factors - either extremely small (under 15 bits) or extremely large (over 243 bits) - provide little attack surface. This creates a "safe zone" at the extremes of the factor size distribution.

Erdős and Kac [@ErdosKac1940] showed that the number of prime factors $\omega(n)$ in typical integers follows a normal distribution centered on $\log\log n$:

$$ \frac{\omega(n) - \log\log n}{\sqrt{\log\log n}} \xrightarrow{d} \mathcal{N}(0,1) $$

For 256-bit numbers, this means most integers have roughly 4-5 distinct prime factors of varying sizes which is precisely the balanced configurations that Cheon's attack exploits. Secure configurations (dominated by one large prime factor) lie in the tails of this distribution.

Our trial division filter systematically rejects candidates with small factors, skewing the factor distribution toward Cheon's safe zone. The $2^{16}$ trial division limit ensures that any remaining small factors are negligible, pushing the factorization toward the "one large prime" regime where Cheon's attack provides no advantage. Combined with our selection of curves with extremely high embedding degrees (on the order of 253-256 bits for our proposed curves), pairing-based attacks become computationally infeasible. This rigidity provides a form of parameter transparency: by constraining factors beyond minimum requirements, we reduce the space for hidden structure that future attacks might exploit.

Our Methodology

The process is broken into a sequence of steps that follow the map-reduce pattern to process the outputs of previous steps, intermediate data is stored in a SQLite database e.g. data/256.sqlite3 which can be queried and analyzed.

Steps

We start with 2.1 billion numbers, filter them in steps, and then finally score and rank the resulting curves.

1. Congruent Primes

As the $2^{31}$ bit range is comparatively small the whole space can be quickly enumerated and each prime is identified by a 31-bit value. Only primes with the desired congruence properties are recorded:

• $p \equiv 1 \pmod{3}$ - Required for the existence of primitive cube roots of unity in $\mathbb{F}_p$, enabling the GLV endomorphism $\phi(x,y) = (\zeta_3 x, y)$ [@Silverman1994§III.9]
• $p \equiv 3 \pmod{4}$ - Combined with the above constraint, this gives $p \equiv 7 \pmod{12}$, which ensures exactly six isomorphism classes of curves with j-invariant 0 over $\mathbb{F}_p$, corresponding to cosets of sixth powers in the multiplicative group [@Silverman1994§II.5]

This leaves us with 2,854,800 congruent primes out of approximately 22m primes.

2. Cornacchia Decomposition

Internally we represent these primes in the form of $a^2 + 3 b^2$ as it maps neatly to the Eisenstein integers via $c = a+b$, $d = 2 b$. Cornacchia's algorithm is guaranteed to decompose our filtered primes into the desired form.

The Lattice structure overlaid on the coefficient space of the Eisenstein integers shows each intersection point can have a GLV compatible prime (marked with a +) on either side of it. Only two of the orders can be prime, all twists are immediate neighbours of the prime, the lattice repeats in an 18x12 grid.

3. Factor via Trial-Division

To prepare for the next step, which requires the field $p$ to be factored, we select curves with a known factorization pattern which is quickly computable. We achieve this via trial division with a $2^{16}$ limit, and marking those where the remainder is prime. This narrows the the results by a factor of ~100 down to 202,843 primes with known factors.

4. Multiplicative Generator

The curve equation $y^2 = x^3 + g^i$ requires the generator of the multiplicative field $\mathbb{F}_p^\times$ of order $p-1$, as the sextic twists are selected by the power of the generator modulo 6. We record the lowest $g$ such that $1 &lt; g &lt; p-1$, such that when mapped to the 6th primitive roots of unity they identify different twists.

5. Sextic Twist Enumeration

Every prime in our congruency class maps to a family of six curve twists, the orders $\vec{q}$ of these twists are deterministic as they are coefficient neighbors of the Eisenstein representation of $p$ from $\mathbb{F}_p$.

As shown in Section \ref{prime-order-vs-trace-structure}, only two specific isomorphism classes can potentially yield prime-ordered curves. The the two values are $g^1$ and $g^5$, we say the order $q_i$ of the curve $E_{p,i}$ is represented by $g^i$. Two curves with coefficients $b_1$ and $b_2$ are isomorphic precisely when $b_1/b_2$ is a sixth power in $\mathbb{F}_p^*$ [@Silverman1994§II.4.1]. This relates directly to the cyclotomic extension $\mathbb{F}_p(\zeta_6)$ and the sixth cyclotomic polynomial $\Phi_6(x) = x^2 - x + 1$ [@Washington2008§10.5].

We record the generator power which, which Eisenstein coordinate offsets the curve order maps to, and whether the order is prime. If the curve is anomalous it's discarded.

This leaves us with 6971 prime ordered twists, graphed above as the $(a,b)$ coordinates of their base field, and the modular relationship between them.

6. GLV Verification

The GLV endomorphism requires $\lambda$ and $\beta$ to be complimentary 3rd primitive roots of unity in their respective fields [@Silverman1994§III.9]. The curve is tested to ensure the endomorphism retains the groups order, this is essentially a 'self test' phase which confirms all the remaining curves have the desired endomorphism, the optimal parameters for scalar decomposition are found by permuting the signs of the parameters $(\lambda,\beta,b_1,b_2)$. However, while most curves were found to permit efficient decomposition, a few don't.

7. Twist Order factors

For j-invariant 0 curves with GLV optimization, each prime field generates 6 twists. In x-coordinate protocols, adversaries can force computation on unintended twists as they share the same field, making all twist orders potentially security-critical. Unlike classical prime relationships ($p+2$ twins, Sophie Germain pairs), our central primes satisfy $p \equiv 7 \pmod{12}$ and occupy one of two positions within the Eisenstein lattice. Each prime's neighborhood consists of Eisenstein coefficients $(c,d)\pm{1}$, we factor both p-1 and all curve orders, plus curve orders $\pm{1}$.

Analysis extends beyond small-subgroup attacks to include Cheon's generalized discrete logarithm attacks exploiting medium-sized factors across twist families, with the exception that safe primes in the form of $2q+1=p$ will have embedding degree $k=1$.

8. Embedding Degree

The smallest value $k$ where $p^k \equiv 1 \pmod{q}$ defines the size of the extension field where the EC-DL problem transfers to a DL problem in a field. The EC-DL problem in $E_p$ with $\approx 2^t$ security transfers to a DL problem in $F_{p^k}$ with complexity roughly $O(\sqrt{p^k}) \equiv O(p^{k/2})$. Security is maintained when $p^{k/2} \ge 2^t$, but breaks down when $k$ is small enough that $p^{k/2}$ becomes computationally feasible. Beyond practical thresholds ($k \ge 2^{64}$), the extension field becomes too large for any feasible attack, making the embedding degree irrelevant to security analysis.

Distance Metric & Ideal

The rigidity argument depends on factorization patterns of the prime field $p-1$, curve orders $q$, their multiplicative groups $q-1$, and all six twist orders. These patterns follow established statistical distributions from number theory, forming a probability space where curves with optimal security properties are proportionally rare.

For each factorization, we compute the ratio of the largest factor's bit-length to the field's bit-length:

$$\text{score}(n) = \frac{\log_2(\text{largest prime factor of } n)}{L}$$

where $L$ is the target bit-length (256). Multiple scores are then combined using an aggregation function $\eta$ which balances average performance against worst-case outliers:

$$\eta(\vec{x}) = \frac{1}{2}\left(\sqrt{\frac{1}{n}\sum_i x_i^2} + \frac{1}{n}\sum_i x_i\right)$$

This averages the RMS and arithmetic mean, penalizing low outliers so that a single weak factor pattern degrades the overall score. Metrics are aggregated hierarchically (prime curve order, non-prime twists, field factorization), then normalized to $[0, 1]$ which measures the distance from an unachievable ideal where all factorizations would be prime.

For reference, the curves detailed in the Appendix are:

• p256kNG score: 0.93
• secp256k1 score: 0.72
• lowest ranked score: 0.42

:::

\pagebreak

References & Citations

::: {#refs} :::

\pagebreak

Proposed Curves

p256kNG (GargleBlaster-1633357673-p256sw64glv)

p = 2^256 - 2^32 - 1633357673 = a^2 + 3b^2 = c^2 + d^2 - cd
  = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe9ea4f097
(a,b): (280665280308630755699599450204595059522, 111084186793311435752294492815031882631)
curve: y^2 = x^3 + g^5   note: g=3, g^5 = 243
|E_p_5|=q: 0xfffffffffffffffffffffffffffffffe3223b98768d0b19e6f2b5d396cc87ac1
 E_p_5 G: (0x2,0xb44504aafcbf2737dfdfeb88b15f79650c7aef0fe4e3d79ee9cf442d1e252994)
embedding degree log2: 256.0
glv     lambda: 13^((q-1)/3) = 0x6f966d22b0abd72dee7fec497ef17a6250d2b2eaf5ed04819ddd1495e8f7206f
	  beta: 5^((p-1)/3) = 0x8ba4aa64f9dfec95af30a0bfb3994286b0cd12ed7e980d3a8d60d02dfc422ff4
	   b_1: 0x7f94216f05961ab34c2c354383d727bb
	   b_2: 0xfffffffffffffffffffffffffffffffd8affa702a00417c74cd7267895c5d3b4
	   g_1: 0xa7241284c8cc99d7225436c0d702a70e2d8bc65ba06327bb195c3b9080257325
	   g_2: 0x7f94216f05961ab34c2c354383d727bbe62b86a04264159fdd15f6747ec1e2fc
	   decomposition: log2(k1)=126 log2(k2)=127 score=1.01015625
factor(p-1) = 2 * 3 * 0x2aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa6fc62819
twist g^0 = 2^2 * 3^2 * 7 * 409 * 0xdf3 * 0xbab59a280c6c1dcccf0bc524793aa789f742c3973099c1f752b9de501
twist g^1 = 13 * 43 * 61 * 331 * 367 * 0xb5c7949e93e5ba3f7fe565f * 0x175d11fb41ca62964b49abfcb16db8168b
twist g^2 = 3 * 7 * 19 * 79 * 0x30fd * 0x38b0f * 0x31101387dd81c34c07bae9e7dd107257d3b2ed119c7742e8915d5
twist g^3 = 2^2 * 43 * 211 * 0x10ba9 * 0x1ba2540ff2d2faa21081ff57aabbc63fa85717ce9849e8d4ac52b295f
twist g^4 = 3 * 373 * 0x89b * 0xf67 * 0x741e5 * 0xf9621f9188f43247d31e8472279152be7bb1e83bb21cd35a9cb
twist g^5 - 1 = 2^6 * 3 * 0x155555555555555555555555555555552ed84f75f366b977de98f26f73bb5f9
twist g^5 = 0xfffffffffffffffffffffffffffffffe3223b98768d0b19e6f2b5d396cc87ac1 prime
score: 0.9265256121473879
rank: 1.0

secp256k1 for comparison

p = 2^256 - 2^32 - 977 = a^2 + 3b^2 = c^2 + d^2 - cd
  = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
(a,b): (335665926241849821909543298348372613710, 32251486774603278314292522680766854539)
curve: y^2 = x^3 + g^5   note: g=3, g^5 = 243
|E_p_5|=q: 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
 E_p_5 G: (0x1,0x7140656225f00a89990bf533811640b8c5698558df1362051bd4ecc033b6f0a2)
embedding degree log2: 253.42
glv     lambda: 3^((q-1)/3) = 0x5363ad4cc05c30e0a5261c028812645a122e22ea20816678df02967c1b23bd72
	  beta: 2^((p-1)/3) = 0x7ae96a2b657c07106e64479eac3434e99cf0497512f58995c1396c28719501ee
	   b_1: 0xe4437ed6010e88286f547fa90abfe4c3
	   b_2: 0xfffffffffffffffffffffffffffffffe8a280ac50774346dd765cda83db1562c
	   g_1: 0x3086d221a7d46bcde86c90e49284eb153daa8a1471e8ca7fe893209a45dbb031
	   g_2: 0xe4437ed6010e88286f547fa90abfe4c4221208ac9df506c61571b4ae8ac47f71
	   decomposition: log2(k1)=127 log2(k2)=125 score=1.01015625
factor(p-1) = 2 * 3 * 7 * 0x3481 * 0x1db8260e5e3b460a46a0088fccf6a3a5936d75d89a776d4c0da4f338aafb
twist g^0 = 2^2 * 3 * 0x4c0adce6b * 0x44f88d6d38d7fb2eb5243f * 0x10a92c5ee5bf7a047e73a880d8afd1a11b
twist g^1 = 0x1ad4f * 0xc60379 * 0x16d79f1f * 0x8a3da1572042fac2e762092c5262d37282e48ba91f99bab
twist g^2 = 3^2 * 13^2 * 0xcf7 * 0x586f * 0x99ee564ea5d84f508913936a761b0d5d792a426a7779817ae2f5b67
twist g^3 = 2^2 * 7^2 * 0x2a97 * 0x50baa1 * 0x285b3b1fb * 0x14d8c7ebee77 * 0x79359f7ae8e5adb8e5369a249f8c93f329
twist g^4 = 3 * 199 * 0x4a23 * 0x116023db004e34dad1d * 0x15d0e0bcdf566f48c735475f7fe29571630e5909f
twist g^5 - 1 = 2^6 * 3 * 149 * 631 * 0x17d6cfb8ee30c51 * 0x978c6f353c3889a79 * 0x10dbff26eab8198050172ee03275
twist g^5 = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141 prime
score: 0.7282360672666071
rank: 0.5970227812343563

\pagebreak

Low-Scoring Curve for Comparison

The progression reveals distinct optimization strategies across the mathematical landscape. The p256kNG curve demonstrates systematic parameter selection, where each component contributes to overall structural coherence through clean factorizations and consistent mathematical relationships. secp256k1 represents the middle ground - a curve selected without explicit optimization that exhibits mixed complexity patterns, functional but carrying the irregularities typical of less rigorous selection processes.

This comparison curve illustrates the opposite approach, where parameters are more distant in a mathematically elegant sence and show more scattered structural irregularities. The substantial scoring difference between the three examples captures meaningful structural differences rather than marginal improvements.

p = 2^256 - 2^32 - 779818409 = a^2 + 3b^2 = c^2 + d^2 - cd
  = 0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffed184ea57
(a,b): (218759355458312614062595609125638953582, 150484144942005796825567969123892872263)
curve: y^2 = x^3 + g^5   note: g=3, g^5 = 243
|E_p_5|=q: 0xfffffffffffffffffffffffffffffffe07c9e786d2fa95b4548f9018a27d4315
 E_p_5 G: (0x1,0x71ea3f1dd15e2078372ca755fd3e743278373df85fba34c1b2d0e751c0602274)
embedding degree log2: 253.68
glv     lambda: 25^((q-1)/3) = 0x9acccdc991fb30e068533f087c58abd19d2effc914c2e8e211d80826a4108eaf
	  beta: 3^((p-1)/3) = 0x563db126ae96379311048781275adf65b671f4f75d32ace0cbc62347ee0d5d9f
	   b_1: -0x335d53c5f3e99709433890316bde9627
	   b_2: -0xfffffffffffffffffffffffffffffffd255d852d366cac132073a03e40e8ba88
	   g_1: 0xe26c62599c8de9a1341befda6194888ebdf53a22816324586df34c2fd26addcd
	   g_2: 0x335d53c5f3e99709433890316bde9627652a978673f4f9ee8a0806d54fd8663b
	   decomposition: log2(k1)=124 log2(k2)=125 score=1.0109375
factor(p-1) = 2 * 3 * 5 * 13 * 29 * 37 * 263 * 0x22db * 0x438b * 0x56b1 * 0x59ff * 0x23a5560457fdb1e6e3a676c19badf2220db4f8d45bf9
twist g^0 = 2^2 * 3^2 * 7 * 0x7c873 * 0x46f7b45 * 0x150123d270b1 * 0x5bd10404eb5df74f055f8c514b6d96bef6bb0ecf
twist g^1 = 73 * 163 * 877 * 0x40465 * 0x17d67771 * 0x4f621c7b * 0x1b3466f9c1ab2b92a1e1 * 0x826da38b5dff81e4c867
twist g^2 = 3 * 103 * 0xb77bd * 0x127e9bb2f1f373c89ee8c22213b9dae4cd3aa044f05236304d624bcd3b
twist g^3 = 2^2 * 7^2 * 31 * 0x1231 * 0x3517 * 0x4c5d0398ac8d3777 * 0x995b04936f2209202ffad51b0a3f55efd29a063
twist g^4 = 3 * 5^2 * 229 * 541 * 0xa2a5d0501 * 0x6649fe247223968bce977 * 0x71cd3c85f5b1f17ec261c81613575
twist g^5 - 1 = 2^2 * 3 * 5 * 0x5bebf * 0xbe1f124ce81f2fe40e205824a8bc7eb60aff1a986ac09e2ae62d4d67d5
twist g^5 = 0xfffffffffffffffffffffffffffffffe07c9e786d2fa95b4548f9018a27d4315 prime
score: 0.42672460328214423
rank: 0.0

\pagebreak

Mathematical Foundations

Deterministic Curve Order Mapping via Eisenstein Integers in $\mathbb{Q}(\sqrt{-3})$

The history of elliptic curve point counting has rich and deep roots which have been refined over the decades, we can trace a lineage of sorts which leads to the most useful results for us:

• In 1986: Lenstra [@lenstra1986elliptic, 11, §4] provides an intuitive formula for j-invariant 0 curves over $\mathbb{Q}(\sqrt{-3})$, which comes surprisingly close to Wu & Xu's [@GuangwuXu_2020_1136] conclusions in 2020.
• In 1995: Schoof [@schoof1995counting§4] explains how to count the number of points when the endomorphism ring of E is known.
• In 2005: Nogami and Morikawa [@Nogami2005] propose a method to obtain the six orders of these curves by counting the order of only one curve.
• In 2006: Hess, Smart, and Vercauteren [@Hess_Smart_Vercauteren_2006_110] propose similar methods for twists $\phi_d : E' \mapsto E$ over extension fields $\mathbb{F}_{q^d}$ where $d = 6$ if $j(E) = 0$.
• In 2018: Kim, Bahr, Neyman and Taylor [@kim2018orders§2.1] then completely characterize, by j-invariant, the number of orders of elliptic curves over all finite fields $F_{p^r}$ using combinatorial arguments and elementary number theory.

We present a simple, explicit and computationally efficient method for a deterministic mapping between the isomorphisms $E_{p,j} : y^2=x^3+g^j$ where $j=j \bmod{6}$, and their orders using properties of Eisenstein integers and primitive characters:

• Any prime $p \equiv 7 \pmod{12}$ can be represented as $p = c^2 - cd + d^2 = a^2 + 3b^2$.

• This corresponds to a prime ideal factorization $(p) = \pi\bar{\pi}$ in the ring of Eisenstein integers $\mathbb{Z}[\omega]$, where $\pi = c + d\omega$ and $\omega = e^{2\pi i/3}$.

• The orders of the six curves $E_j: y^2 = x^3 + g^j$ correspond to the norms of the six elements $\pi \pm{{1,\omega,\omega^2}} \in \mathbb{Z}[\omega]$, where $p + 1 + \text{Trace}(u) = N(\pi + u) = |E_j|$, which we define as traces =

  • traces[0] = $\text{Trace}(1) = - 2a = - 2c + d$
  • traces[1] = $\text{Trace}(\omega^2) = - a - 3b = - c - d$
  • traces[2] = $\text{Trace}(\omega) = a - 3b = c - 2d$
  • traces[3] = $\text{Trace}(- 1) = 2a = 2c - d$
  • traces[4] = $\text{Trace}(- \omega^2) = a + 3b = c + d$
  • traces[5] = $\text{Trace}(- \omega) = -a + 3b = - c + 2d$

  A lookup table for the coefficients $(t_0 c) + (t_1 d)$ of traces[i] can be stated simply as:

        t = [(-2,1), (-1,-1), (1,-2), (2,-1), (1,1), (-1,2)][i%6]

We have empirically verified that the set of curve orders matches the set of traces, they represent the Eisenstein neighborhood of $p$. However, the specific mapping between the generator index $j$ of $g^j$ and the index $i$ of traces[i] depends on the chirality and orientation w.r.t the Eisenstein lattice. We solve this mapping in a novel way:

• Find the canonical $(a,b)$ to represent $p = a^2 + 3b^2$ (e.g. using Cornacchia's algorithm)
  • Where $a$ is even, $b$ is odd, and both are positive integers
• Derive $c = a + b$ and $d = 2b$

We can then utilize a lookup table, indexed by:

• $f: {0,1}^2 \to {0,1,2,3}$
  • $f(u_0,u_1) \to 2 u_0 + u_1$
  • $u_0: 1$ if $c+d \equiv 2 \pmod{3}$ else $0$
  • $u_1 = 1$ if $\zeta_3(g) \cdot c + d \equiv 0 \pmod{p}$, else $0$

When $n | (p-1)$, $\zeta_n(x)$ denotes $x$'s character in the primitive $n$-th roots of unity via $x^{(p-1)/n} \bmod p$. The resulting $f$ provides a bijection between the traces and the power of the generator $g$:

• $f(u_0,u_1) = 0$: $\text{traces}[i] + p + 1 \leftrightarrow |E_j| : y^2 = x^3 + g^{(0, 1, 2, 3, 4, 5)[i]}$
• $f(u_0,u_1) = 1$: $\text{traces}[i] + p + 1 \leftrightarrow |E_j| : y^2 = x^3 + g^{(0, 5, 4, 3, 2, 1)[i]}$
• $f(u_0,u_1) = 2$: $\text{traces}[i] + p + 1 \leftrightarrow |E_j| : y^2 = x^3 + g^{(3, 4, 5, 0, 1, 2)[i]}$
• $f(u_0,u_1) = 3$: $\text{traces}[i] + p + 1 \leftrightarrow |E_j| : y^2 = x^3 + g^{(3, 2, 1, 0, 5, 4)[i]}$

The four permutations form the Klein four-group $V_4$, corresponding to automorphisms of the trace index set that preserve the quadratic twist pairing ${0,3}, {1,4}, {2,5}$. This method provides a complete and deterministic characterization of the distinct six isomorphism classes of j-invariant 0 curves over $\mathrm{GF}(p)$ when $p \equiv 7 \pmod{12}$.

This method requires 3 modular exponentiations: finding $\sqrt{-3}$ for Cornacchia's algorithm, computing $\zeta_3(g)$ for the $u_1$ classification bit, and verifying $g$ is a primitive root. The remaining operations are table lookups and simple integer arithmetic without negative intermediates. This computes all six curve orders simultaneously, compared to approaches requiring separate computations for each curve.

On the $u_1$ bit and the cubic character: The $u_1$ bit bridges two independent structures: the Eisenstein prime $\pi = c + d\omega$ from Cornacchia, and the generator $g$. The quotient $\mathbb{Z}[\omega]/(\pi)$ embeds into $\mathbb{F}_p$ sending $\omega \mapsto -c/d$, so $-d/c = \omega^{-1}$ is always a primitive cube root of unity. The cubic character $\zeta_3(g)$ measures how $g$ aligns with this structure - since $g$ is chosen independently (as the smallest primitive root), this alignment cannot be determined from $(c, d)$ alone, requiring the modular exponentiation. Note that when only searching for prime-order curves, $u_1$ can be skipped: use $u_0$ to identify which pair of orders can be prime, then test both.

Prime Order vs Trace Structure

For curves $E_{g^i}: y^2 = x^3 + g^i$ where $g$ generates $\mathbb{F}^*/\mathbb{F}^{*6}$, at most two of the six curves can have prime order [@Broker2005; @Washington2008, §4.1]. The specific pair depends on the mapping between trace indices and curve indices (determined by the classification bits from the previous section). This constraint is explained by the structure of the trace of Frobenius:

• Let $t_i$ be the trace of Frobenius for curve $E_{g^i}$, so that $|E_{g^i}| = p + 1 - t_i$ [@Silverman1986, §V.2]

• For j-invariant 0 curves over fields with $p \equiv 7 \pmod{12}$, the traces follow a specific pattern related to the sixth roots of unity [@Silverman1994, §II.2]:

  $t_i = \alpha \cdot \zeta_6^i + \beta \cdot \zeta_6^{-i}$

  where $\alpha$ and $\beta$ are constants and $\zeta_6$ is a primitive sixth root of unity in the field.

• For $i \in {0, 3}$, the orders are always even (hence composite for $p &gt; 3$):

  • $t_0 = -2a$ gives $|E_0| = p + 1 + 2a$ (even, since $p \equiv 7 \pmod{12}$ implies $p+1$ is even, and $a$ is even in Cornacchia's representation)
  • $t_3 = 2a$ gives $|E_3| = p + 1 - 2a$ (even)

• For the remaining indices ${1, 2, 4, 5}$, exactly one pair has orders divisible by 3, depending on $a \bmod 3$:

  • If $a \equiv 1 \pmod{3}$: orders at indices 1 and 5 are divisible by 3
  • If $a \equiv 2 \pmod{3}$: orders at indices 2 and 4 are divisible by 3
  • (Note: $a \not\equiv 0 \pmod{3}$ since otherwise $3 | a^2 + 3b^2 = p$, contradicting $p \equiv 1 \pmod{3}$)

• This leaves at most 2 trace indices where the order could potentially be prime. For $p &gt; 7$, all six orders exceed 3, ensuring this divisibility analysis is complete. (The edge case $p = 7$ admits an order of exactly 3.)

• The six traces form quadratic twist pairs: $t_i + t_{i+3} = 0$ for $i \in {0,1,2}$. Consequently, each pair of orders sums to $2(p+1)$, and the sum of all six orders equals $6(p+1)$.

GLV $\beta$ from Eisenstein Coordinates

The GLV endomorphism $\phi(x,y) = (\beta x, y)$ requires $\beta$ to be a primitive cube root of unity in $\mathbb{F}_p$. From the Eisenstein representation $\pi = c + d\omega$, the quotient $-d/c$ is itself a primitive cube root (for $p &gt; 3$), so:

$$\beta \in {-d/c, (-d/c)^2} = {g^{(p-1)/3}, g^{2(p-1)/3}} \mod p$$

The choice between these two values depends on the Eisenstein lattice orientation, analogous to the $u_0, u_1$ classification bits for curve order mapping.