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!
 A: 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?
A: 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.
A: 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).
