在椭圆曲线上生成随机点

Question

我正在编写一个程序，它在一定的时间间隔内随机选择两个整数。我还写了一个 class（我没有在下面添加）它使用两个数字 'a' 和 'b' 并创建了一个椭圆曲线的形式： y^2 = x^3 + ax + b

我编写了以下内容来创建两个随机数。

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

现在我想在这条椭圆曲线上生成一个随机点。我该怎么做？

Answer 1

曲线有无限长，至于每个y ϵ ℝ至少有一个x ϵ ℝ使得(x, y) 在曲线上。因此，如果我们谈到曲线上的一个随机点，我们就不能希望随机点在整条曲线上均匀分布。

但如果这不重要，你可以取一个y在某个范围内的随机值，然后计算以下函数的根：

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

这将产生三个根，其中两个可能是复数（不是实数）。您可以从中随机取一个实根。这将是随机点的 x 坐标。

在 numpy 的帮助下，求根很容易，所以这是在曲线上获取随机点的函数，给定 a 和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]

在 repl.it 上查看运行。

在椭圆曲线上生成随机点

Generate a random point on an elliptical curve

elliptic-curve

python-3.x

differential-equations