Division polynomials of elliptic curves over finite fields

Jung Hee Cheon, S. HahnProceedings of the Japan Academy Series A Mathematical Sciences 1996 · DOI

Abstract: We consider an elliptic curve $E$ over the finite field $\mathbb{F}_p$ for a prime $p \neq 2, 3$. This paper provides a mathematical characterization of division polynomials for these curves, distinguishing between supersingular and ordinary cases to derive explicit forms for $p^k$-th division polynomials.

Introduction

In the study of elliptic curves, division polynomials are essential tools. For an elliptic curve $E$ and an integer $n$, the $n$-th division polynomial $\psi_n(x, y)$ is a function whose roots correspond to the $x$-coordinates of the $n$-torsion points (points $P$ such that $nP = \mathcal{O}$).

While the general properties of these polynomials are well-understood in characteristic zero, their behavior in "characteristic $p$" (where the field size is a power of a prime $p$) presents unique challenges. Specifically, the behavior of $p$-torsion points differs drastically depending on whether a curve is ordinary or supersingular. This work by J. Cheon and S. Hahn (1996) fills a gap in the literature by providing explicit formulas and structural properties for these polynomials when $n$ is a power of the characteristic $p$.

Theoretical Framework

The authors work with curves in the standard Weierstrass form: $$y^2 = x^3 + Ax + B$$ over a finite field $\mathbb{F}_p$ (for $p \neq 2, 3$). The analysis relies on several key mathematical pillars:

  • Frobenius Endomorphism: The map $\phi_q: (x, y) \mapsto (x^q, y^q)$ is a central tool. In finite fields, the multiplication-by-$q$ map is intimately related to this Frobenius map.
  • Recursive Identities: The authors utilize standard identities relating $\psi_{mn}$ to $\psi_m$ and $\psi_n$ to build proofs for $p^k$.
  • Polynomial Reduction: A critical technical result (Lemma 2) establishes that if $q$ divides $n$, then the division polynomials $\phi_n$ and $\psi_n^2$ are actually polynomials of $x^q$, significantly restricting their possible algebraic forms.

Characterizing the Supersingular Case

The most striking insight of the paper is the "collapsed" nature of division polynomials for supersingular curves. Because a supersingular curve has no non-trivial $p$-torsion points in the algebraic closure, the $p$-th division polynomial $\psi_p$ cannot have roots.

Theorem 1 proves that for a supersingular curve over $\mathbb{F}_p$, the $p$-th division polynomials are:

  • $\psi_p(M) = -1$
  • $\phi_p(M) = x^{p^2}$
  • $\omega_p(M) = y^{p^2}$

This generalizes for $q = p^k$, where $\psi_q(M) = (-1)^k$. These results show that for supersingular curves, the $q$-th division polynomials are exactly the coordinates of the $k$-th power Frobenius map.

Characterizing the Ordinary Case

In the ordinary case, the curve possesses $p$-torsion points, and the structure of the division polynomial reflects this. However, the polynomial still exhibits a highly specific "compressed" form.

Theorem 2 demonstrates that for an ordinary curve, the $q$-th division polynomial ($q=p^k$) satisfies: $$\psi_q(M) = g(x)^q$$ where $g(x)$ is a separable polynomial of degree $(q-1)/2$. This reveals a hidden symmetry in the distribution of torsion points for ordinary curves, showing that the polynomial is a perfect $q$-th power of a simpler underlying polynomial.

Conclusion and Applications

While this work is theoretical, it provides the foundation for several practical applications in computational number theory. By explicitly defining the structure of $p^k$-torsion, these results are potentially useful for:

  1. Schoof's Algorithm: Optimizing point-counting algorithms by exploiting the known structure of division polynomials in characteristic $p$.
  2. Cryptography: Analyzing the security of elliptic curve pairings, where the structure of $p^k$-torsion is a critical factor in determining the embedding degree and moving between groups.

Although the paper assumes $p \neq 2, 3$ to simplify the Weierstrass equations, the methodology provides a roadmap for approaching binary and ternary fields, which are also highly relevant to modern cryptographic implementations.

Summary updated

Abstract

We consider an ellipic curve E over the finite field Fp for a prime p 4= 2,3.
BibTeX
@inproceedings{cheon1996division,
  author = {Jung Hee Cheon and S. Hahn},
  title = {{Division polynomials of elliptic curves over finite fields}},
  booktitle = {Proceedings of the Japan Academy Series A Mathematical Sciences},
  year = {1996},
  doi = {10.3792/pjaa.72.226},
}
Figure