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:
- Schoof's Algorithm: Optimizing point-counting algorithms by exploiting the known structure of division polynomials in characteristic $p$.
- 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