Elliptic Curves – Determining Size of m-Torsion Group Over Finite Fields

elliptic-curvesfinite-fieldssagemathtorsion-groups

In this paper by De Feo the following is stated (in proposition 4):

Let $E$ be an elliptic curve defined over a field $k$, and let $m\neq 0$ be an integer. The $m$-torsion group of $E$, denoted by $E[m]$, has the following structure:

  • $E[m]\simeq(\mathbb Z / m \mathbb Z)^2$ if the characteristic of $k$ does not divide $m$;
  • If $p>0$ is the characteristic of $k$, then
    \begin{equation}
    E[p^i] \simeq
    \begin{cases}
    \mathbb Z/p^i\mathbb Z & \textrm{for any } i\geq 0, \textrm{or} \\
    \{ \mathcal O \} & \textrm{for any } i\geq 0.
    \end{cases}
    \end{equation}

Moreover, an elliptic curve such that $E[p^i]\simeq \{\mathcal O\}$ for any $i\geq 0$ is called supersingular, whereas the other curves are called ordinary.

However, I have trouble seeing the validity of this theorem.
I also cannot seem to replicate these statements in Sage.

My ideas about some definitions

As far as I understand the torsion subgroup of an elliptic curve over the rational numbers are precisely the points that have finite order (these points can then be found using the Nagell-Lutz theorem).

I guess that the $m$-torsion group are precisely the points $P$ such that $[m]P=\mathcal O$, as a result the $2$-torsion points must have $y=0$.

An example which do not seem to hold

Let $E$ be the elliptic curve $y^2=x^3+1$ and let $k$ be the (finite) field $\mathbb F_{17}$, let $m=2$.
The characteristic of $k$ is, logically, $17$.

Now, since the characteristic of $k$ does not divide $m$ we must have that
$E[2] \simeq (\mathbb Z/2\mathbb Z)^2$.
It seems to me that we must have that the number of elements in $E[2]$ must thus equal $2^2 = 4$.
However, the following Sage code tells me that there are only 2 points of order 2 on the finite curve $E$ instead of the expected 4.

m = 2
k = GF(17)
E = EllipticCurve(k, [0, 1])

print([pt for pt in E.points() if m*pt == E(0, 1, 0)])

Another example which does not hold

Using the same $E$ and $k=\mathbb F_{13}$ as above we must have (since $p=13>0$ is the characteristic of $k$) that
$E[13^i] \simeq \mathbb Z/13^i \mathbb Z$ for any $i \geq 0$ (since $E$ is ordinary over $k$ according to Sage).
Using similar code as above, I can only get $\mathcal O$ as element of $E[13^i]$.

Another thought

I have seen many other references talk about the algebraic closure of $k$ (which most denote as $\bar k$).
I do not see how this would help redefine the proposition by De Feo in any way, nor does it help me get anywhere in Sage as elliptic curves over algebraic closures of finite fields have numerous different properties and functions.

Conclusion

Any answer or remark to one of the following questions will be highly appreciated

  1. The reasoning behind the proposition by De Feo at the top.
  2. When is a curve supersingular and how can we see this by checking the order of points in Sage?
  3. Where have I gone wrong in my examples?

Best Answer

It may not be immediately obvious from a cursory reading, but an underlying assumption in the stated result (by De Feo as well as in Silverman's book) is that it deals with the torsion parts of the group $E(\overline{k})$. In other words, $E[m]$ stands for the group of $m$-torsion points defined over an algebraic closure of $k$. If you want to specifically look at the $m$-torsion of the group of points with coordinates in the field $k$, you need a different notation such as $E(k)[m]$ (I'm afraid I don't know what is the standard notation here — caveat reader).

The upshot: To see all of the $m$-torsion of an elliptic curve you need to include the points with coordinates in selected (algebraic) extension fields of the field of definition $k$.

Further points:

  1. When the curve $E$ is defined over a finite field $k$, then the description based on divison polynomials implies that all the points in $E[m]$ have coordinates in a finite extension field $k'$, $[k':k]<\infty$. The same applies to curves defined over $\Bbb{Q}$, but that is of less concern here.
  2. If $k=\Bbb{F}_q$ is a finite field of cardinality $q$, and $E$ is an elliptic curve defined over $k$, then the Hasse-Weil bound says that the number of $k$-rational points of $E$ is a group of size $\le q+1+2\sqrt q$. So if $p$ is a prime number $>q+1+2\sqrt q$ it is impossible for the group $E(k)$ to have any $p$-torsion. Therefore you should not be surprised to learn that to find non-trivial points in $E[p]$ you need to go to an extension field $k'=\Bbb{F}_{q^m}$ (with the exponent $m$ not necessarily easy to figure out).
  3. The same phenomenon appears in elliptic curves that are easier to visualize. Consider the curve $E$ defined by $y^2=x^3+x$ over the field of real numbers $\Bbb{R}$. Its $2$-torsion points are $(0,0),(i,0),(-i,0)$ and the point at infinity. Four of them altogether, as prescribed by the cited theorem, but two with coordinates in the extension field $\Bbb{C}$.

Hopefully this clears up some of the fog.

About testing for supersingularity. I don't know how Sage does this, but I add a few suggestions:

  • Theorem 4.1. from chapter V of Silverman's book (reference number 66 in De Feo's article) states that a curve defined over a finite field $K$ of characteristic $p$, $p>2$, by a Weierstrass equation $$y^2=f(x)$$ with $f$ a cubic without repeated roots (in $\overline{K}$) is supersingular if and only if the coefficient of $x^{p-1}$ in $f(x)^{(p-1)/2}$ vanishes. Applied to $f(x)=x^3+1$, $p=13$, we see that $$f(x)^6=x^{18}+6 x^{15}+15 x^{12}+20 x^9+15 x^6+6 x^3+1.$$ Here the coefficient of $x^{12}$ is $15\not\equiv0\pmod{13}$, so the curve is ordinary.
  • Doing the same knowing the size of $E(\Bbb{F}_q)$ alone is possible but a bit trickier. It is known (Hasse-Weil-Davenport) that if we have $$\# E(\Bbb{F}_q)=q+1-\omega_1-\omega_2$$ for complex numbers $\omega_1,\omega_2$ that also satisfy $\omega_1\omega_2=q$ (these two equations determine $\omega_{1,2}$ uniquely) then for all extension degrees $r>1$ $$\# E(\Bbb{F}_{q^r})=q^r+1-\omega_1^r-\omega_2^r.$$ In the example curve we have $q=13$ and can easily calculate (or let Sage do it) that $\# E(\Bbb{F}_{13})=12.$ It follows that $\omega_{1,2}=1\pm 2\sqrt{3}i$. A bit of testing then reveals that $$\# E(\Bbb{F}_{13^{12}})=23298094520064$$ is divisible by $13^2$. So we have $13^2$-torsion points defined over $\Bbb{F}_{13^{12}}$.

See Chapter V in Silverman's book for more of the theory. Judging from my recent but brief encounter with the use of supersingular curves in cryptography that theory is very relevant to you!

Related Question