Return to Answer

1. By using random scalar and scalar multiplication

   1. Choose a generator point $P$ on the curve
   2. Get random integer between $0 < k < \text{Order of the Group}$
   3. Calculate $R =[k]P$ by scalar multiplication, prefably executing by double-and-add algorithm.

2. Using random element with sample rejection on the curve equation.

   1. Choose a random element $x \in \mathbb{Z_{25}}$.

   2. Check the equation $y^2 = x^3 + x + 1$ has a solution, i.e. it is a quadratic residue.

      If there is no solution return to 1. step ( reject the sample)

      Else, we have two solutions, $y$ and $-y$ (or one $y=-y$). These values can be found using the Tonelli-Shank algorithm and its generalizations.

   3. Now use the random source to select $\bar{y}$ as $y$ or $-y$, or toss a coin.

   4. Form the random point on the curve as $R=(x,\bar{y})$

   Note that, the point at infinity cannot be expressed in affine-coordinates without some tricks. Therefore, this method cannot return the point at infinity. If the point at infinity is also required on the random selection, one can select it with an initial random. Select it within $\frac{1}{\text{Order of The Group}}$ probability. Then use the above.

3. If you are using SageMath then it has a function

   random_element() and the explanation is given as

   Return a random point on this elliptic curve, uniformly chosen among all rational points.

   SageMath random_element() function uses the 2. method with an addition that it can also return the point at infinity, $\mathcal{O}$

1. By using random scalar and scalar multiplication

   1. Choose a generator point $P$ on the curve
   2. Get random integer between $0 < k < \text{Order of the Group}$
   3. Calculate $R =[k]P$ by scalar multiplication, prefably executing by double-and-add algorithm.

2. Using random element with sample rejection on the curve equation.

   1. Choose a random element $x \in \mathbb{Z_{25}}$.

   2. Check the equation $y^2 = x^3 + x + 1$ has a solution, i.e. it is a quadratic residue.

      If there is no solution return to 1. step ( reject the sample)

      Else, we have two solutions, $y$ and $-y$ (or one $y=-y$). These values can be found using the Tonelli-Shank algorithm and its generalizations.

   3. Now use the random source to select $\bar{y}$ as $y$ or $-y$, or toss a coin.

   4. Form the random point on the curve as $R=(x,\bar{y})$

   Note that, the point at infinity cannot be expressed in affine-coordinates without some tricks. Therefore, this method cannot return the point at infinity. If the point at infinity is also required on the random selection, one can select it with an initial random. Select it within $\frac{1}{\text{Order of The Group}}$ probability. Then use the above.

3. If you are using SageMath then it has a function

   random_element() and the explanation is given as

   Return a random point on this elliptic curve, uniformly chosen among all rational points.

   SageMath random_element() function uses the 2. method with an addition that it can also return the point at infinity, $\mathcal{O}$

One should not call this function for a large group. There is a theory behind this and this can be found in the book, however, the reference can go back to J. W. S. Cassels, 1966, Diophantine Equations with Special Reference To Elliptic Curves

One should not call this function for a large group. There is a theory behind this and this can be found in a book such as Washington's book, however, the reference can go back to J. W. S. Cassels, 1966, Diophantine Equations with Special Reference To Elliptic Curves

One should not call this function for a large group. There is a theory behind this;

Theorem: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_p} \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with $n_1|n_2$.

One should not call this function for a large group. There is a theory behind this and this can be found in the book, however, the reference can go back to J. W. S. Cassels, 1966, Diophantine Equations with Special Reference To Elliptic Curves

Theorem: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_n} \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with $n_1|n_2$.