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

edit

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 ?

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.

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.