SAGE random point on elliptic curve with a specific order

Question

I am playing around with SAGE and elliptic curves. Is there a way to pick a point at random on an elliptic curve with a specific order that I choose?

I use the function random_point(), but the order of the returned point is virtually random. Are there any smart way besides iteratively call random_point() until a point with the desired order is found?

Thanks! :D

Answer 1

You could take a look at the elements within the torsion subgroup of your curve:

E = EllipticCurve([1, 0, 0, -45, 81]);
print [(P, P.order()) for P in E.torsion_subgroup()]

[((0 : 1 : 0), 1), ((0 : 9 : 1), 10), ((6 : 3 : 1), 5), ((-6 : -9 : 1), 10), ((18 : -81 : 1), 5), ((2 : -1 : 1), 2), ((18 : 63 : 1), 5), ((-6 : 15 : 1), 10), ((6 : -9 : 1), 5), ((0 : -9 : 1), 10)]

Then you can try and do something random yourself based upon that perhaps?

Answer 2

Over what field is your elliptic curve defined? Let's look at two cases:

$E/\mathbb{Q}$: here the answer by Warren Moore is easiest, the torsion subgroup gives you an easy way to find a point of the order you want.

$E/\mathbb{F}_p$: here, take a look at the number of rational points $\#E(\mathbb{F}_p)$. Does the order $n$ you want divide this? Then try taking any random $x \in \mathbb{F}_p$, calculate if there is a corresponding $y \in \mathbb{F}_p$ so that $P = (x, y)$ defines a rational point on $E$.

Then, for $k = \frac{\#E(\mathbb{F}_p)}{n}$ either $k \cdot P$ is a point of order $n$, or it is the point at infinity. In the latter case, repeat with a new random $x$.

All in all, such a point $P$ has probability $\frac{n - 1}{n}$ of giving you an $n$-order point, so you're almost always ready the first try.