ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 22 May 2020 16:35:53 +0200How can I find number of elements of n-torsion points on an elliptic curve over finite field?https://ask.sagemath.org/question/51114/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.
Tue, 28 Apr 2020 18:18:55 +0200https://ask.sagemath.org/question/51114/how-can-i-find-number-of-elements-of-n-torsion-points-on-an-elliptic-curve-over-finite-field/Answer by dan_fulea for <p>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.</p>
https://ask.sagemath.org/question/51114/how-can-i-find-number-of-elements-of-n-torsion-points-on-an-elliptic-curve-over-finite-field/?answer=51503#post-id-51503Hello, 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.
Fri, 22 May 2020 16:35:53 +0200https://ask.sagemath.org/question/51114/how-can-i-find-number-of-elements-of-n-torsion-points-on-an-elliptic-curve-over-finite-field/?answer=51503#post-id-51503