How to generate a random point on curve efficiently?

[Po-Chu Hsu]

I have an application that needs to use a random number generator to generate a point on an elliptic curve.

The typical way is

1. generate random integer x.

2. Calculate Y = xG.

Integer x(prg, Integer::One(), group.GetMaxExponent());

ECP::Point Y = group.ExponentiateBase(x);

However, in my application, this takes too much time, and I don't need to know x.

I tried another approach.

1. generate random integer x.

2. calculate the corresponding y by using the function of the curve.

3. if y doesn't exist, find x + 1 until there's a valid y.

Integer x(prg, Integer::One(), this->p_);

ECP::Point Y;

bool v = x.GetBit(0);

while (true) {

Integer r = (a_exp_b_mod_c(x, Integer("3"), p) + (a * x) % p + b) % p;

Integer y = a_exp_b_mod_c(r, q, p);

if (a_exp_b_mod_c(y, Integer::Two(), p) == r) {

if (v) {

Y = ECP::Point(x, y);

} else {

Y = ECP::Point(x, this->p_ - y);

}

break;

}

x += 1;

}

This method is much faster than the first approach.

However, it is still slower than my expectation.

Does anyone have good advice?