Ask Your Question
2

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

asked 2016-12-05 17:16:21 +0200

Bahamut91 gravatar image

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!

Thank you for your help!

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
1

answered 2016-12-05 20:23:53 +0200

Vova gravatar image

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.

edit flag offensive delete link more

Comments

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 ?

tmonteil gravatar imagetmonteil ( 2016-12-05 21:52:35 +0200 )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.

Vova gravatar imageVova ( 2016-12-06 15:17:39 +0200 )edit
1

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.

nbruin gravatar imagenbruin ( 2016-12-09 21:57:07 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-12-05 17:16:21 +0200

Seen: 2,760 times

Last updated: Dec 05 '16