立方殘基模質數

-2

我想解x方程x^3 + 1 = 0模p。 p是素數。我在https://eprint.iacr.org/2009/457.pdf 立方殘基模質數

上實現我的代碼我得到正確答案p％3 == 2，但p％2 = 1錯誤答案。任何人都可以幫助我嗎？

import java.io.*; 
import java.util.*; 
import java.math.*; 

class cube_root { 
    public static void main(String[] args) { 
     Scanner sc = new Scanner(System.in); 
     long a = sc.nextInt(); 
     long p = sc.nextInt(); 
     long x = f(a, p); 
     System.out.println(x); 
    } 

    public static long f(long a, long p) { 
     if (p == 2) { 
      return 1; 
     } 
     if (p == 3) { 
      return 2; 
     } 
     long q = GCD(3, p - 1); 
     long x = powmod(a, (p - 1)/q, p); 
     if (x != 1) { 
      return -1; 
     } 
     long m = p - 1; 
     long s = 0; 
     for (; m % 3 == 0; m /= 3) { 
      s++; 
     } 
     long t = m; 
     long k = m/3; 
     long rem = m % 3; 
     long b = 0; 
     for (long i = 2; i < p; i++) { 
      long g = GCD(3, p - 1); 
      long y = powmod(i, (p - 1)/g, p); 
      if (y != 1) { 
       b = i; 
       break; 
      } 
     } 
     long c = powmod(b, t, p); 
     long r = powmod(a, t, p); 
     long h = 1L; 
     long cp = powmod(c, (long)Math.pow(3, (int)s - 1), p); 
     c = inv(c, p); 
     for (long i = 1; i < s; i++) { 
      long d = powmod(r, (long)Math.pow(3, (int)(s - t - 1)), p); 
      if (d == cp) { 
       h *= c; 
       r *= (c * c * c); 
      } else if (d != 1 || d == cp * cp) { 
       h *= (c * c); 
       r *= ((c * c * c) * (c * c * c)); 
      } 
      c = powmod(c, 3, p); 
     } 
     r = h * powmod(a, k, p); 
     if (rem == 1) { 
      r = inv(r, p); 
     } 
     return r; 
    } 

    public static long GCD(long a, long b) { 
     if (b == 0) { 
      return a; 
     } 
     return GCD(b, a % b); 
    } 

    public static long powmod(long a, long p, long n) { 
     long r = a % n; 
     if (p == 0) { 
      return 1; 
     } 
     if (p == 1) { 
      return r; 
     } 
     if (p % 2 == 1) { 
      r = powmod(a, p/2, n) % n; 
      r = r * r % n; 
      return r * a % n; 
     } else { 
      r = powmod(a, p/2, n) % n; 
      r = r * r % n; 
      return r; 
     } 
    } 

    public static long inv(long a, long p) { 
     return powmod(a, p - 2, p); 
    } 
}

來源

2014-12-02 user2784016

這需要'算法'標記，我不確定它是否適合在這裏或數學stackexchange更好。 – 2014-12-02 16:06:09

我在我提到的論文中找到了算法。我試圖執行。我想我在某個地方犯了一個小錯誤。我無法找到它。 :( – user2784016 2014-12-02 16:24:25

請爲你的函數和變量使用更好的名字，這是什麼？我們怎麼能理解你很容易做什麼？ – Lrrr 2014-12-02 16:28:26

沒有太多的在紙上的算法的研究，我建議您調試程序，然後查看這些錯誤：

（代碼段被選擇只是在於向世人證明錯誤，你將需要仔細檢查這個程序實際上不會與它應該做的）

1溢出錯誤

如

long r = powmod(a, t, p); 
... 
r *= ((c * c * c) * (c * c * c));

long可能不適合你在這裏做什麼不夠大。

長度的範圍大約是2^64，而cuberoot的大約是2642245.在這種情況下不會很難溢出。可以考慮使用BigInteger。

2的接一個錯誤

例如

for (; m % 3 == 0; m /= 3) { 
    s++; 
}

確實s得到增加，因爲它應該是？再來一次？少一點時間？

來源

2014-12-03 03:25:00

立方殘基模質數

回答

相關問題