SAGE random point on elliptic curve with a specific order

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

• Perhaps someone at ask.sagemath can answer this. Dec 4, 2016 at 14:53

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?

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.