Generate a random point on an elliptical curve

Question

I'm writing a program which randomly chooses two integers within a certain interval. I also wrote a class (which I didn't add below) which uses two numbers 'a' and 'b' and creates an elliptical curve of the form: y^2 = x^3 + ax + b

I've written the following to create the two random numbers.

def numbers():
n = 1
while n>0:
    a = random.randint(-100,100)
    b = random.randint(-100,100)
    if -16 * (4 * a ** 3 + 27 * b ** 2) != 0:
        result = [a,b]
        return result
    n = n+1

Now I would like to generate a random point on this elliptical curve. How do I do that?

Answer 1

The curve has an infinite length, as for every y ϵ ℝ there is at least one x ϵ ℝ so that (x, y) is on the curve. So if we speak of a random point on the curve we cannot hope to have a homogeneous distribution of the random point over the whole curve.

But if that is not important, you could take a random value for y within some range, and then calculate the roots of the following function:

    f(x) = x³ + ax + b - y²

This will result in three roots, of which possibly two are complex (not real numbers). You can take a random real root from that. This will be the x coordinate for the random point.

With the help of numpy, getting the roots is easy, so this is the function for getting a random point on the curve, given values for a and b:

def randomPoint(a, b):
    y = random.randint(-100,100)
    # Get roots of:  f(x) = x^3 + ax + b - y^2
    roots = numpy.roots([1, 0, a, b - y**2])
    # 3 roots are returned, but ignore potential complex roots
    # At least one will be real
    roots = [val.real for val in roots if val.imag == 0]
    # Choose a random root among those real root(s)
    x = random.choice(roots)
    return [x, y]

See it run on repl.it.