Finding random point of specified order using MAGMA

Question

I would like to use MAGMA to construct a random point of specified order on an elliptic curve over a finite field. I have created the elliptic curve E0, but I'm not sure how to get the subgroup of points of a fixed order. There is a solution to this problem for general groups here in the answer by verret, but trying to follow that produces an error:

> p := 2^216 * 3^137 - 1;
> Fp2 := GF(p^2);
> E0 := EllipticCurveWithjInvariant(Fp2 ! 1728);
> AbE0 := TorsionSubgroup(E0);
> PremE0 := CosetAction(AbE0, sub<AbE0|>);
>> PremE0 := CosetAction(AbE0, sub<AbE0|>);
                        ^
Runtime error in 'CosetAction': Coset table not finite

I tried this code with a small "toy" example of an abelian group and it worked fine, so I'm wondering if the issue is that the size of AbE0 is just too large? AbE0 is finite, but (very) large.

Finally, is there a better way of doing this for elliptic curves? Even if I am able to turn the group of points on E0 into a permutation group and use the suggestions in the link to get the subgroup of order I'm interested in, then pick a random element, I will eventually want to use that element as a point on the curve, so I would need to translate back again. It seems there should be a better path...

Answer 1

I don't think there's a built-in command to do this automatically in Magma, but it can be done using a few facts about elliptic curves and cyclic groups. Let $k = \mathbb{F}_{p^2}$. First, $E(k)$ is the direct sum of at most $2$ cyclic groups. (See here, for example.) For your curve, running

> [Factorization(Order(el)) : el in Generators(AbE0)];
[
[ <2, 216>, <3, 137> ],
[ <2, 216>, <3, 137> ]
]

we see that $\newcommand{\Z}{\mathbb{Z}} E(k) \cong \frac{\Z}{2^{216} 3^{137} \Z} \oplus \frac{\Z}{2^{216} 3^{137} \Z}$. Calling these generators $P_1$ and $P_2$, then $Q_1 := 3^{137} P_1$ and $Q_2 := 3^{137} P_2$ generate the subgroups of order $2^{216}$ in their respective factors. Thus, any point of order $2^{216}$ in $E(k)$ can be written as $m_1 Q_1 + m_2 Q_2$ where $\gcd(2, m_1, m_2) = 1$. So to generate a random point of order $2^{216}$, it suffices to pick random $m_1$ and $m_2$ with these properties.