how to generate the n-torsion group - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T11:43:37Z http://mathoverflow.net/feeds/question/38127 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38127/how-to-generate-the-n-torsion-group how to generate the n-torsion group Sarah 2010-09-09T01:28:41Z 2010-09-09T20:11:36Z <p>Hello,</p> <p>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 <a href="http://en.wikipedia.org/wiki/Weil_pairing" rel="nofollow">http://en.wikipedia.org/wiki/Weil_pairing</a>). 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?). </p> <p>Thank you!</p> http://mathoverflow.net/questions/38127/how-to-generate-the-n-torsion-group/38131#38131 Answer by Emerton for how to generate the n-torsion group Emerton 2010-09-09T01:49:24Z 2010-09-09T01:49:24Z <p>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.)</p> <p>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)$.)</p> <p>There are quite possibly better algorithms than this direct one, but I will let someone with more expertise weigh in on that.</p> <p>If you mean something else by "how are they generated?", then maybe you could explain more.</p> <p>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?</p> http://mathoverflow.net/questions/38127/how-to-generate-the-n-torsion-group/38147#38147 Answer by Robin Chapman for how to generate the n-torsion group Robin Chapman 2010-09-09T06:27:55Z 2010-09-09T06:57:59Z <p>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.</p> <p>Assume that we know the order of $E(\mathbb{F}_q)$, by <a href="http://en.wikipedia.org/wiki/Schoof%2527s_algorithm" rel="nofollow">Schoof's algorithm</a> or by one of its improvements. Also assume that we can factor this order completely.</p> <p>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]$.</p> <p>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$.</p> <p>Note that the Weil pairing can be computed using <a href="http://crypto.stanford.edu/miller/" rel="nofollow">Miller's algorithm</a> 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.</p> http://mathoverflow.net/questions/38127/how-to-generate-the-n-torsion-group/38224#38224 Answer by Victor Miller for how to generate the n-torsion group Victor Miller 2010-09-09T20:11:36Z 2010-09-09T20:11:36Z <p>Look in section 6 of my article "The Weil Pairing and its efficient calculation" <a href="http://tcs.uj.edu.pl/~mistar/pdf/Miller2004WeilPairing.pdf" rel="nofollow">http://tcs.uj.edu.pl/~mistar/pdf/Miller2004WeilPairing.pdf</a> . It has the details that you want (much along the lines of Robin Chapman's answer).</p>