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

See: `lemma/2-eisenstein-mapping-magic.py`

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] expains 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$ 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[0]` = $\text{Trace}(\omega^2)   = - a - 3b   = - c - d$
  * `traces[0]` = $\text{Trace}(\omega)     = a - 3b     = c - 2d$
  * `traces[0]` = $\text{Trace}(- 1)        = 2a         = 2c - d$
  * `traces[0]` = $\text{Trace}(- \omega^2) = a + 3b     = c + d$
  * `traces[0]` = $\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. 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: \zeta_2(a b d) = 1$
  * $u_1: \zeta_3(g) c + d = 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 \text{\\#}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 \text{\\#}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 \text{\\#}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 \text{\\#}E_j : y^2 = x^3 + g^{(3, 2, 1, 0, 5, 4)[i]}$

While the specific order of our traces in relation to the mapping indices are somewhat arbitrary, they can be thought of as permutations of the Dirichlet characters $\chi_9$ or $\chi_7$. 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 aformentioned method requires 3 modulo exponentiations, which includes finding $\sqrt{-3}$ for Cornacchia's algorithm, and two integer square roots. The remaining operations are either table lookups, or simple binary and integer arithmetic without negative intermediates. This computes all six curve orders simultaneously, compared to approaches requiring separate computations for each curve.