# Pick a point at random on an elliptic curve with specific order

Hi!

I use the function random_point() to pick a point at random on an elliptic curve, but I was wondering if there is a way to pick a point at random that has a specific order (or some useful geometric property that allows me to do that).

So far, brute forcing seems the only way to me (pick a point at random, check its order and iterate until it has the wanted order) but it's obviously very naive!

edit retag close merge delete

Sort by » oldest newest most voted

Let n be the order of your curve. Let k be desired order of the point. Let P be the random point that you obtained. Compute Q = (n/k)*P With high probability, Q will have order k. Check that. If Q is not of order k, pick a new random point P and repeat the process.

more

Given the fact that the distribution of the first random point is uniform (as guaranteed in the doc), how is the distribution of the probability among the points of order k with your method ?

( 2016-12-05 14:52:35 -0500 )edit

It should have the same randomness, but at the level of points of order k. The informal 'proof': if you have a set of random points, which you multiply all by the same scalar (n/k), then you will get a 'compressed with respect to order k', set, which will carry through the randomness to that level.

( 2016-12-06 08:17:39 -0500 )edit

If you know that the group of order k points on your elliptic curve is cyclic, this approach is fine. However, if it is not, you might miss points:

Suppose E(k)= (Z/2) x (Z/64) , so that the order is n=128 and you want to select a point of order 2 (at random). Then the proposed approach would amount to picking a point P (likely of order 64) and. (n/2)P is guaranteed to be the identity element. Adjusting the approach by computing Q=32P will only give you the non-trivial 2-torsion point that is divisible by 2; never the other.

( 2016-12-09 14:57:07 -0500 )edit