如何找到橢圓曲線的最小y座標y^2 = x^3 +

如何在有限域F（p）上找到橢圓曲線y^2 = x^3 + ax + b的最小y座標？在SAGE中，a和b大約10^15的數量級，整數p非常大，大約爲10^45的數量級。我需要在SAGE中找到它，並且我一直在嘗試很多方法。我發佈了一些我的代碼：如何找到橢圓曲線的最小y座標y^2 = x^3 +

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:'

以上只是帶有隨機數的示例代碼。任何建議或完全不同的想法也會非常有幫助。

非常感謝 JS

來源

2014-04-24 user3567036

這只是一個側面觀察：這種深刻的縮進使我非常懷疑 - 一種經典的「代碼味道」。在你的情況下，如果p2 [1]> 0和ZZ（p2 [1]） 0並且ZZ（p2 [0]）

如果x> = 0 y的最小值是sqrt（b）... –

您可以嘗試Shanks-Tonelli算法（http://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm），但問題是找到最小的y。你可以嘗試所有的x值，這似乎是低效的。 –

的橢圓曲線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

給人的點（544771569075032357553369359272826923818637077：1：1）內的第二的1/10。

我試着用上面的素數p和下面的5000個隨機值a和b來看看我多久才能得到y的哪個值作爲最小值。只是爲了給你一些關於它在實踐中會有多好的感覺。

來源

2014-04-24 16:49:08 koffie

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不是質數。

來源

2014-04-24 16:59:46

如何找到橢圓曲線的最小y座標y^2 = x^3 +

回答

相關問題