How to generate the n-torsion group in an elliptic curve

Question

Let $E$ be an elliptic curve over a field $K$. I was curious about the following sentence: "then the $n$-torsion on $E(\overline{K})$ has known structure, as a Cartesian product of two cyclic groups of order $n$" (found at https://en.wikipedia.org/wiki/Weil_pairing). There is no citation in the Wikipedia article to follow up with, but I am interested in generating these cyclic groups when E is defined over $\mathbb{F}_q$ and am wondering if there is a known way of doing this or what these groups will actually be (i.e., how are they generated?).

Thank you!

Answer 1

The standard reference for these sorts of facts is Silverman's book "The arithmetic of elliptic curves". The statement is that the $n$-torsion subgroup of $E(\overline{K})$, which is naturally a $\mathbb Z/n\mathbb Z$-module (because it is an abelian group of exponent $n$), is actually free of rank 2 over that ring (or, more concretely, it is isomorphic to the product of two cyclic groups of order $n$). In fact, if $K$ has positive characteristic $p$ (which is the case you are interested in) one needs the additional hypothesis that $p$ does not divide $n$; otherwise the statement is not true. (This is discussed carefully in Silverman's book.)

What do you mean by "how they are generated"? Do you mean to find explicit generators, i.e. assuming that your elliptic curve has the form $y^2 = f(x)$ with $f(x)$ cubic (as you may, at least when $p$ is odd), to find an explicit pair of points $(x_1,y_1)$ and $(x_2,y_2)$ lying on the curve and defined over $\overline{\mathbb F}_q$ which generate the $n$-torsion subgroup (for some $n$)? If so, the classical way to do this is by finding roots of the so-called division polynomials: these are polynomials in $x$, whose coefficients can be written as (more and more complicated, the larger $n$ is) expressions in the coefficients of $f$, and whose roots are precisely the $x$-coordinates of the points of $E$ of exact order $n$. (To find the corresponding $y$-coordinates one then just solves $y^2 = f(x)$.)

There are quite possibly better algorithms than this direct one, but I will let someone with more expertise weigh in on that.

If you mean something else by "how are they generated?", then maybe you could explain more.

EDIT: I just saw your clarification. If $E[n] \subset E(\mathbb F_q)$, then $n$ will necessarily be fairly small, since the order of $E(\mathbb F_q)$ is bounded above by $1+ q + 2\sqrt{q}$ (the Hasse--Weil bound). In this case the division polynomials will have some roots defined over $\mathbb F_q$, and you can find them explicitly given enough computing power and the equation of $E$. Is this what you want?

Answer 2

Under the assumption that $E[n]\subseteq E(\mathbb{F}_q)$, to compute $E[n]$ I'd avoid using division polynomials, as they rapidly become cumbersome. Rather I would generate random elements of $E[n]$ until I have a generating set.

Assume that we know the order of $E(\mathbb{F}_q)$, by Schoof's algorithm or by one of its improvements. Also assume that we can factor this order completely.

This is how I'd generate random elements of $E[n]$. Pick a random point $P$ on $E(\mathbb{F}_q)$. One can do this by picking an $x$-coordinate randomly and solving, if possible, a quadratic equation to get the $y$-coordinate. As we know the prime factors of the order of $E(\mathbb{F}_q)$ we can find the order of $P$ in this group, and write this order as $mn'$ where $n'$ is the highest common factor of the order of $P$ and $n$. Then computing $[m]P$ gives an element of $E[n]$.

After generating enough elements of $E[n]$, we should be able to find a two-element "basis" of the group. (I'll omit details here; this can certainly be done by reducing to the prime power case, but perhaps it can be done more generally). One ends up with two points $P$ and $Q$. These points have order $n$ and their Weil pairing $e(P,Q)$ is a primitive $n$-th root of unity $\zeta$.

Note that the Weil pairing can be computed using Miller's algorithm or more recent alternatives. Given a point $R\in E[n]$ we can find $a$ and $b$ with $R=aP+bQ$ by using the Weil pairing: $$e(R,Q)=e(aP+bQ,Q)=e(P,Q)^ae(Q,Q)^b=\zeta^a$$ etc.

Answer 3

Look in section 6 of my article "The Weil Pairing and its efficient calculation" http://tcs.uj.edu.pl/~mistar/pdf/Miller2004WeilPairing.pdf (Wayback Machine)¹. It has the details that you want (much along the lines of Robin Chapman's answer).

¹Miller, Victor S., The Weil pairing, and its efficient calculation, J. Cryptology 17, No. 4, 235-261 (2004). ZBL1078.14043.