Generating a random point on an elliptic curve over a finite field

I have coded an implementation of elliptic curves in order to apply some of the ECC algorithms. However, in most of them, Alice needs to choose a point P on a given curve. What is the general procedure for selecting such a point?

Given a small example such as $$y^2 = x^3 + x + 1$$ over $$F_{25}$$, is there an algorithm to generate a random point on the curve? In my implementation points on this field are represented by polynomials, if that is relevant.

• You could find a generator $G$, compute a random scalar $n$, and use $[n]G$; or you could do rejection sampling on a random $x$ coordinate until $x^3 + x + 1$ is a quadratic residue, and then pick the sign of $y$ by flipping a coin. But what do you want to do with your random curve point? If, for example, you need to generate two points for which you can convince someone else you don't know a discrete-log relation in order to use Pedersen commitments—and you're not a Swiss voting authority—then you need to put a little more work into it. – Squeamish Ossifrage Apr 8 at 1:30

is there an algorithm to generate a random point on the curve?

By having a good random source as /dev/urandom you can generate random point as follows;

1. Choose a generator point $$P$$
2. Get random integer between $$0 < k < \text{Order of the Group}$$
3. Calculate $$R = k P$$ by scalar multiplication.

In my implementation points on this field are represented by polynomials, if that is relevant.

The $$\mathbb{F}_{25}$$ is an Extension Field and it is usual to represent the elements of the field by the polynomial representation which is very advantageous on operations. As a result, the coordinates of points have polynomial representation.

• I've read about generator points but I've found that not necessarily there is a point that generates the whole group. For example, taking the curve $y^2 = x^3 + x + 2$ over $F_{25}$, I used Sage to calculate the order of each point: (sagecell.sagemath.org/…) and it can be seen that even though the cardinality of the group is 32 the biggest order is 16. Is it just a matter of chosing an EC with prime cardinality? – srb Apr 7 at 19:42
• See this answer – kelalaka Apr 7 at 20:02