MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## how to generate the n-torsion group

Hello,

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 http://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!

-
 Sorry, I just wanted to clarify my question. I am familiar with the result that $E[n]$ is isomorphic to $\mathbb{Z}/n\mathbb{Z}×\mathbb{Z}/n\mathbb{Z}$, so the focus should be on the second part of the question, which is that if I have $E[n]\subseteq E(\mathbb{F}_q)$, what are these cyclic groups and how exactly are they being generated? – Sarah Sep 9 2010 at 1:38

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?

-
 This could be what I want, although it's true I was hoping for an algorithm that is, as you say, "better than this direct one." To be more specific about what I am ultimately interested in, if we write $G = E[n]$ and then $G = G_1\times G_2$ for these cyclic groups of order $n$, I was hoping to find efficiently computable maps $f:G\rightarrow G_1$ and $g:G\rightarrow G_2$, which I assumed (perhaps incorrectly) would be related somehow to the structure of the groups themselves. – Sarah Sep 9 2010 at 3:06

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.

-
 Heuristically we only need to generate 4 (3 point something really) n-torsion points to get a basis of the group, if I recall correctly some article about generators of finite abelian groups. Also, in practice, probably easier to compute $N/nP$ for random $P$ and check for order $n$, replacing the factoring $N$ stage with factoring $n$. – Dror Speiser Sep 9 2010 at 20:29 @Dror: if you look in my article on calculating the Weil Pairing (link in my answer to this question), there's a section working out this probability. The answer is not quite as good as you've given -- the worst case is when $n$ is the product of the first $k$ primes. Basically the number is bounded by $n/\phi(n)$ where $\phi$ is Euler's phi-function. – Victor Miller Sep 19 2010 at 2:56

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

-