如何找到椭圆曲线 y^2 = x^3 + 的最小 y 坐标

1 投票

2 回答

657 浏览

提问于 2025-04-18 04:03

我想知道如何在有限域 F(p) 中找到椭圆曲线 y^2 = x^3 + ax + b 的最小 y 坐标。这里的 a 和 b 都很大，大约在 10^15 的数量级，而整数 p 也非常大，大约在 10^45 的数量级。我需要在 SAGE 中找到这个值，已经尝试了很多方法。下面是我写的一些代码：

    maxtime=120960000
    p = 976324781263478623476912346213469128736427364
    a = 783468734639429
    b = 98347874287423
    E = EllipticCurve(GF(p),[a,b])
    length =50
    for i in range(1,maxtime):
        e = ZZ.random_element(999999999999)
            if E.is_x_coord(I) == true:
                temp = E.lift_x(I)
                break
    i=0
    print 'P1:'
    print temp
    length=0
    t=50
    count=2
    p2=temp+temp
    while count < 10000000000:
        count=count+1
        p2=p2+temp
        if (p2[1]>0):
            if (ZZ(p2[1]) < ZZ(p-1)):
                if (p2[0] > 0):
                    if( ZZ(p2[0]) < ZZ(p-1)):
                        if E.is_x_coord(p2[0]) == true:
                            y2 = E.lift_x(p2[0])
                            length=len(str(y2[1]))
                            if length <=11:
                                print 'p2:'
                                print y2
                                print 'count:'
                                print count
                                break
                            if t > length:
                                t= length
                                print 'length:'
                                print t
                                print 'count:'
                                print count
                                print 'p2:'
                                print y2
    print 'failed:'

上面的代码只是用随机数字写的示例代码。如果你有任何建议或者完全不同的想法，也会非常有帮助。

非常感谢！
J S

算法 sage 大数计算数论有限域椭圆曲线最小坐标

2 个回答

在GF(p)这个数学结构中，元素之间没有自然的顺序。你提到的“最小y”，我猜是指整数上的通常顺序。这里有个例子，假设p=17，a=11，b=3。这个例子的解是y=3，x=4。

sage: K = GF(17)
sage: a, b = 11, 3
sage: _.<X> = K[]
sage: P = X^3 + a*X + b
sage: next(((P - y^2).roots(), y) for y in K if (P - y^2).roots())
([(4, 1)], 3)
sage: 3^2 == P(4)
True

要注意，你的p不是一个质数。

回答于 2025-04-18 由 Python大师

分享举报

椭圆曲线E至少有p+1-2p^{1/2}个点，当p很大的时候，(p+1-2p^{1/2})/p几乎等于1。这意味着，平均来说，每个y值都有一个对应的x值，使得(x,y)在这条椭圆曲线上。这也就是说，除非有什么奇怪的情况发生，我会期待最小的y值会非常小（我通常认为它会是0、1或2）。这表明，从小到大尝试不同的y值在实际操作中会非常快。但我并没有证明这总是会很快，因为如果真的发生了什么奇怪的事情，最小的y值实际上很大，那就会花费很长时间。

p = next_prime(976324781263478623476912346213469128736427364)
a = 7834684394239111322316457
b = 98347872833141
E = EllipticCurve(GF(p),[a,b])
Fx.<x> = GF(p)[]
f = x^3 + a*x + b
for y in GF(p):
    xs=(f-y^2).roots(multiplicities=False)
    if len(xs)>0:
        x = xs[0]
        P = E(x,y)
        print P
        break

在不到1/10秒的时间内给出了点(544771569075032357553369359272826923818637077 : 1 : 1)。

我尝试了5000个随机的a和b值，使用上面的素数p，下面你可以看到我得到了多少次哪个y值是最小值。这只是为了让你对这个方法在实际中效果有个大概的了解。

回答于 2025-04-18 由 Python大师

分享举报

如何找到椭圆曲线 y^2 = x^3 + 的最小 y 坐标

2 个回答

撰写回答