Diffie-Hellman - 原始根模塊n - 密碼學問題

-2

在下面的代碼段中，請解釋從第一個「for」循環開始發生了什麼以及爲什麼。爲什麼添加了0，爲什麼在第二個循環中添加了1。 bigi下的「if」語句正在發生什麼。最後解釋一下modPow方法。預先感謝您提供有意義的答覆。Diffie-Hellman - 原始根模塊n - 密碼學問題

public static boolean isPrimitive(BigInteger m, BigInteger n) { 

    BigInteger bigi, vectorint; 
    Vector<BigInteger> v = new Vector<BigInteger>(m.intValue()); 
    int i; 

    for (i=0;i<m.intValue();i++) 
     v.add(new BigInteger("0")); 

    for (i=1;i<m.intValue();i++) 
    { 
     bigi = new BigInteger("" + i); 

     if (m.gcd(bigi).intValue() == 1) 
      v.setElementAt(new BigInteger("1"), n.modPow(bigi,m).intValue()); 
    } 

    for (i=0;i<m.intValue();i++) 
    { 
     bigi = new BigInteger("" + i); 

     if (m.gcd(bigi).intValue() == 1) 
     { 
      vectorint = v.elementAt(bigi.intValue()); 
      if (vectorint.intValue() == 0) 
       i = m.intValue() + 1; 
     } 
    } 

    if (i == m.intValue() + 2) 
     return false; 
    else 
     return true; 

}

來源

2010-05-14 somewhat confused

這顯然是功課。我的問題是：爲什麼人們甚至不想改變他們的問題的文本，似乎有點不同於典型的作業問題？「最後解釋一下modPow的方法。」這讓我大笑。 – Jack 2010-05-14 21:00:41

對待矢量作爲布爾值的列表，其中一個布爾每個號碼0到m。以這種方式查看時，很明顯每個值都設置爲0以將其初始化爲false，然後設置爲1以將其設置爲true。
最後一個循環是測試所有的布爾值。如果它們中的任何一個都是0（表示爲false），則該函數返回false。如果全部都是真的，那麼函數返回true。
解釋你所詢問的if聲明需要解釋一個原始根模塊是什麼，這是函數的全部要點。我認爲如果你的目標是理解這個程序，你應該先了解它實現的是什麼。如果你閱讀它Wikipedia's article，你會在第一段看到這一點：

在模運算，數論的一個分支，一個原根 n爲任意號g財產任何與n互質的數字是與g（mod n）的冪一致。也就是說，如果g是原始根（mod n），那麼對於gcd（a，n）= 1的每個整數a，存在整數k ，使得gk≡a（mod n）。 k被稱爲的一個索引。也就是說，g是整數模n的乘法羣的發生器。

功能modPow工具modular exponentiation。一旦你明白如何找到一個原始根模塊n，你就會明白它。

也許拼圖爲你的最後一塊是要知道兩個數是互質如果他們的最大公約數是1.所以你看到，你粘貼的算法這些檢查。

紅利鏈接：This paper有一些很好的背景，包括如何測試接近結束的原始根。

來源

2010-05-14 20:57:45 indiv

Diffie-Hellman - 原始根模塊n - 密碼學問題

回答

相關問題