ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 09 Dec 2016 21:57:07 +0100Pick a point at random on an elliptic curve with specific orderhttps://ask.sagemath.org/question/35921/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!
Thank you for your help!
Mon, 05 Dec 2016 17:16:21 +0100https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/Answer by Vova for <p>Hi!</p>
<p>I use the function <code>random_point()</code> 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).</p>
<p>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!</p>
<p>Thank you for your help!</p>
https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?answer=35923#post-id-35923Let 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.Mon, 05 Dec 2016 20:23:53 +0100https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?answer=35923#post-id-35923Comment by tmonteil for <p>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.</p>
https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?comment=35924#post-id-35924Given 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 ?Mon, 05 Dec 2016 21:52:35 +0100https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?comment=35924#post-id-35924Comment by Vova for <p>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.</p>
https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?comment=35931#post-id-35931It 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.Tue, 06 Dec 2016 15:17:39 +0100https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?comment=35931#post-id-35931Comment by nbruin for <p>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.</p>
https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?comment=35974#post-id-35974If 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=32*P will only give you the non-trivial 2-torsion point that is divisible by 2; never the other.Fri, 09 Dec 2016 21:57:07 +0100https://ask.sagemath.org/question/35921/pick-a-point-at-random-on-an-elliptic-curve-with-specific-order/?comment=35974#post-id-35974