# How can I find number of elements of n-torsion points on an elliptic curve over finite field?

Hello, How can I find number of elements of n-torsion points on an elliptic curve over finite field? Is it possible to find points? y^2=x^3+Ax+B is the elliptic curve format.

edit retag close merge delete

Sort by ยป oldest newest most voted

Hello, we do not have too much in the question. So here is my choice of an elliptic curve $E$ defined over my choice of a finite field $F$ of characteristic $p$. Of course, $E(F)$ is a finite group. For a small $n$ we can simply ask for the torsion points with that order. For bigger $n$ we may want to compute first the order of $E(F)$... This works only for small orders. Illustrating code/dialog with interrupting comments:

sage: p = 2020.next_prime()
sage: p
2027
sage: F = GF(p)
sage: E = EllipticCurve( F, [3, 4] )
sage: E.order()
2040
sage: E.order().factor()
2^3 * 3 * 5 * 17


so we expect no torsion point of order $7$. For a "big $n$" we cannot use division polynomials. But we could do this for $n$ among $2,3,4,5,6,8,10,15$ (even if $E$ has big order). Let us exemplify this.

For $n=2$ we can first ask for the corresponding division polynomial.

sage: E.torsion_polynomial(2)
4*x^3 + 12*x + 16
sage: E.torsion_polynomial(2).roots(multiplicities=0)
[2026, 1673, 355]
sage: [ E.lift_x(a).xy() for a in _ ]    # _ is the above list
[(2026, 0), (1673, 0), (355, 0)]


We obtain as expected three $2$-torsion points. (Well, an option all=True is usually needed, we will see it later, but here...) They correspond to the roots of the defining polynomial in $x$...

sage: R.<x> = PolynomialRing(F)
sage: f = x^3 + 3*x + 4
sage: f.factor()
(x + 1) * (x + 354) * (x + 1672)
sage: f.roots(multiplicities=False)
[2026, 1673, 355]


We have the order of $E(F)$, but we can also have its structure group:

sage: A = E.abelian_group()
sage: A
Additive abelian group isomorphic to Z/1020 + Z/2 embedded in Abelian group of points on Elliptic Curve defined by y^2 = x^3 + 3*x + 4 over Finite Field of size 2027


So $E(F)\cong \Bbb Z/1020\oplus \Bbb Z/2$. Here, we expect $4$-torsion elements coming only from the $\Bbb/1020$-part, let us see them:

sage: G.<a,b> = AbelianGroup( [1020, 2] )
sage: G
Multiplicative Abelian group isomorphic to C1020 x C2
sage: [ g for g in G if g.order() == 4 ]
[a^255, a^255*b, a^765, a^765*b]


Here, we see four $4$-torsion elements, the $C_2\cong\Bbb Z/2$-component is either trivial or $b$, i.e. both chances are taken, the first component corresponds to $255$ (so thet $4\cdot 255=1020=0$ in that component) and $3\cdot 255$. We also expect four $4$-torsion elements in $E(F)$. Let us get them via the division polynomial.

sage: f = E.division_polynomial(4)
sage: f_roots = f.roots(multiplicities=False)
sage: points = []

sage: for a in f_roots:
....:     try:
....:         points.extend( E.lift_x(a, all=True) )
....:     except Exception:
....:         pass
....:

sage: [ P.xy() for P in points if P.order() == 4 ]
[(1978, 318), (1978, 1709), (759, 1046), (759, 981)]


We can obtain these points also by using the generators of $E$. Asking for and getting them is possible because of the reduced size of the data...

sage: P, Q = E.gens()
sage: P.order(), Q.order()
(1020, 2)
sage: [ (k*P + n*Q).xy() for k, n in cartesian_product( [[255, 765], [0,1]] ) ]
[(1978, 318), (759, 1046), (1978, 1709), (759, 981)]


Having $P,Q$ as above we can immediately get the points of order $3$, note that $1020/3 = 340$:

sage: [ (k*P).xy() for k in (340, 2*340) ]
[(633, 273), (633, 1754)]


The brutal way to get these points is by listing all of them and getting those of order exactly $3$:

sage: [ P.xy() for P in E.points() if P.order() == 3 ]
[(633, 273), (633, 1754)]


This works because of the reduced size of data.

To have a more pointed answer, please edit the question to have it with pointed details for the application in mind.

more

## Stats

Seen: 210 times

Last updated: May 22 '20