在Zp中是否（（a^x）^ 1/x）== a？ （對於Jablon協議）

Question

我必須實施Jablon的協議（paper），但我一直在坐着一個bug兩個小時。

我對數學不太好，所以我不知道這是我的錯在寫它還是它是不可能的。如果這是不可能的，我不會看到Jablon的協議如何實現，因爲它依賴於（（gP^x）^ yi）^（1/x）= gP^yi的事實。

取下面的代碼。它不起作用。

BigInteger p = new BigInteger("101"); 
    BigInteger a = new BigInteger("83"); 
    BigInteger x = new BigInteger("13"); 
    BigInteger ax = a.modPow(x, p); 
    BigInteger xinv = x.modInverse(p); 
    BigInteger axxinv = ax.modPow(xinv, p); 

    if (a.equals(axxinv)) 
     System.out.println("Yay!"); 
    else 
     System.out.println("How is this possible?"); 

Answer 1

你的問題是，你不能精確計算K ^（1/X）正確。我們需要k ^{（1/x））k}爲x。 Fermat's Little Theorem告訴我們k ^p-1是1 mod p。因此我們想找到y，使得x * y是1 mod p-1，而不是mod p。

所以你想要BigInteger xinv = x.modInverse(p-1);。

如果x與p-1共享一個公因式，這將不起作用。 （你的情況避免了這一點。）爲此，你需要額外的理論。如果p是素數，則如果r，r^2，r^3，...，r ^（p-2）中沒有一個與1 mod p一致，則r是原始根。沒有簡單的算法來生成原始根，但它們很常見，所以通常只需檢查一些。 （對於p = 101，我嘗試的第一個數字是2，原來是一個原始根，83也是。）測試它們似乎很難，但它並沒有那麼糟糕，因爲事實證明（省略了這裏有一堆理論）只需要檢查p-1的因子。例如，對於101，您只需檢查1,2,4,5,10,20,25和50的功率。

現在如果r是原始根，那麼每數mod p是河什麼力量？這就是所謂的discrete logarithm problem，並不簡單。 （難度是RSA的基礎，這是一個衆所周知的加密系統。）你可以通過試用部門來完成。所以嘗試1,2,3，...最終你會發現，例如，83是2^89（mod 101）。

但是，一旦我們知道從1到100的每個數字都是2的某種權力，我們就有了一種計算根的方法。因爲將一個數字提升到x的冪只是將指數乘以x。 2^100是1.所以指數乘以x（mod 100）。

所以假設我們希望y^13是83.那麼對於某些k，y是2^k，使得k * 13是89.如果玩弄Chinese Remainder Theorem，您可以認識到k = 53的作品。因此2^53（mod 101）= 93是89的第13個根。

這比我們以前做的要困難。但是，假設我們想要採用44 mod 101的第5根。我們不能使用簡單的過程，因爲5沒有乘法逆模100。但44是2^15。所以2^3 = 8是第5個根。但還有其他4個，即2^23,2^43,2^63和2^83。