On Orders of Elliptic Curves over Finite Fields

Yujin H. Kim, Jackson Bahr, Eric Neyman, Gregory TaylorRose-Hulman 2018

TL;DR

This paper provides a complete characterization of the possible group orders (number of points) for elliptic curves over any finite field $\mathbb{F}_{p^r}$. By leveraging the $j$-invariant and elementary number theory, the authors extend classical results from Gauss and Weil to determine exactly how many distinct orders a curve can take on, ranging from just two for general curves to six for special cases like $j=0$.

What Problem Does This Paper Address?

In the world of arithmetic geometry and cryptography, elliptic curves are defined by equations like $y^2 = x^3 + Ax + B$. When these curves are defined over a finite field $\mathbb{F}_q$, a fundamental question arises: How many points are on the curve?

While the famous Hasse-Weil bound tells us the order must lie within the interval $[q + 1 - 2\sqrt{q}, q + 1 + 2\sqrt{q}]$, it doesn't specify which integers in that range are actually achievable. This paper fills that gap by categorizing curves based on their $j$-invariant—a value that remains constant for all isomorphic curves. The authors aim to determine the exact number of possible orders for a fixed $j$-invariant across all finite fields, including those where the field order $q$ is a power of a prime ($p^r$).

Methods

The authors employ a mix of combinatorial arguments and elementary number theory, specifically:

  • Twist Techniques: They use "quadratic twists" to relate the orders of different curves. A key lemma proven is that the sum of the orders of a curve and its twist is always $2(q+1)$.
  • Weil’s Theorem: This allows them to extend results from prime fields ($\mathbb{F}_p$) to general finite fields ($\mathbb{F}_{p^r}$) by treating the "trace of Frobenius" as roots of specific polynomials.
  • Polynomial Characterization: For special $j$-invariants (0 and 1728), the authors construct cubic and quartic polynomials whose roots are exactly the possible "traces" (the values that determine the curve's order).
  • Character Theory: They utilize Legendre symbols and residue classes (sextic, quartic, and cubic residues) to partition the possible coefficients $(A, B)$ into sets that yield the same curve order.

Datasets

Not discussed in the paper. As a theoretical mathematics paper, it relies on formal proofs rather than empirical data or benchmarks.

Key Insights and Ideas

  • The $j$-invariant as a Classifier: The paper demonstrates that the $j$-invariant is the primary determinant of how much "variety" exists in curve orders. Most curves ($j \neq 0, 1728$) are relatively "boring," possessing only two possible orders over a fixed field.
  • The Special Cases ($j=0$ and $j=1728$): These curves have higher symmetry (automorphisms), which leads to more possible orders.
  • For $j=0$ (curves of the form $y^2 = x^3 + B$), there can be up to six distinct orders.
  • For $j=1728$ (curves of the form $y^2 = x^3 + Ax$), there can be up to four distinct orders.
  • Supersingularity and Field Extension: The authors show that for certain primes, if the extension degree $r$ is odd, the curve is "supersingular" and has a fixed order of $p^r + 1$. However, if $r$ is even, the "trace" branches out into multiple possible values.
  • Elementary Approach: Unlike many papers in this field that rely on advanced algebraic geometry or modular forms, this work stays within the realm of group theory and field theory accessible to an advanced undergraduate or early graduate student.

Key Results

  • General Characterization: For any $j \notin \{0, 1728\}$, there are exactly two possible orders for elliptic curves over $\mathbb{F}_{p^r}$, expressed as $p^r + 1 \pm t$ for some non-negative integer $t$.
  • Specifics for $j=0$:
    • If $p^r \equiv 2 \pmod 3$ and $r$ is odd, the order is always $p^r + 1$.
  • If $r$ is even, the possible orders are $\{p^r \pm 2p^{r/2} + 1, p^r \pm p^{r/2} + 1\}$.
  • Specifics for $j=1728$:
    • If $p \equiv 3 \pmod 4$ and $r$ is odd, the order is always $p^r + 1$.
  • If $r$ is even, the possible orders are $\{p^r + 1, p^r \pm 2p^{r/2} + 1\}$.
  • Polynomial Roots: The authors successfully proved that the traces of these curves are exactly the roots of specific polynomials (e.g., $x^3 - 3qx - a_1(q)^3 + 3qa_1(q) = 0$ for $j=0$), providing a computational path to find the orders.

Limitations and Future Work

  • Characteristic 2 and 3: The paper explicitly focuses on fields where the characteristic $p > 3$. Elliptic curves in characteristics 2 and 3 have different standard forms and more complex automorphism groups, which were not covered here.
  • Realizability of $t$: While the paper proves that for $j \neq 0, 1728$ there are two orders $p^r + 1 \pm t$, it does not provide a general formula for $t$ for every possible $j$; it focuses more on the number of possible orders rather than the specific value of the trace for an arbitrary $j$.
  • Extension to Higher Genus: A natural next step would be to apply similar combinatorial "twist" arguments to hyperelliptic curves or abelian varieties of higher genus.

Summary updated

Abstract

In this work, we 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. Whenever possible, we state and prove exactly which orders can be taken on.
BibTeX
@inproceedings{kim2018orders,
  author = {Yujin H. Kim and Jackson Bahr and Eric Neyman and Gregory Taylor},
  title = {{On Orders of Elliptic Curves over Finite Fields}},
  booktitle = {Rose-Hulman},
  year = {2018},
}
Figure