生成素數循環群

我正在嘗試在 Java 中實現一個循環組生成器，但我遇到了一些問題。在許多密碼系統中，在密鑰生成階段會表達以下片語。

令 G 是素數階 q 的循環群，並帶有生成器 g

我已經對此進行了一些研究，並且已經能夠實現一個具有模數 p 和生成器 g 的循環組生成器。但是，我目前堅持如何確保生成的組的順序是素數 q。

這就是我所擁有的：

public class CyclicGroup {
   private static final int EQUAL = 0;
   private static final BigInteger TWO = new BigInteger("2");

   private BigInteger p, g;

   public CyclicGroup(int bitLength) {
       init(bitLength);
   }

   private void init(int bitLength) {
       BigInteger q = BigInteger.ZERO;

       while (true) {
           q = CryptoUtil.getPrime(bitLength);
           p = (q.multiply(TWO)).add(BigInteger.ONE); // p = 2q+1

           if (!p.isProbablePrime(40)) {
               continue;
           }

           while (true) {
               g = CryptoUtil.rand(TWO, p.subtract(BigInteger.ONE));

               BigInteger exp = (p.subtract(BigInteger.ONE)).divide(q);

               if (g.modPow(exp, p).compareTo(BigInteger.ONE) != EQUAL) {
                   break;
               }
           }

           break;
       }
   }

   public BigInteger getRandomElement() {      
       return g.modPow(CryptoUtil.rand(BigInteger.ONE, p), p);
   }

   public ArrayList<BigInteger> getElements() {
       // This method is horribly ineffective for large groups and should not be used

       ArrayList<BigInteger> elements = new ArrayList<BigInteger>();

       BigInteger index = BigInteger.ONE;
       BigInteger element = BigInteger.ZERO;

       while (element.compareTo(BigInteger.ONE) != EQUAL) {
           element = g.modPow(index, p);
           elements.add(element);

           index = index.add(BigInteger.ONE); // index++
       }

       return elements;
   }

   public BigInteger getModulus() {
       return p;
   }

   public BigInteger getGenerator() {
       return g;
   }
}

上面的類生成一個模數為 p 的循環群和一個生成器 g。以下程式碼將生成後續範例輸出。請注意，4 的微小位長是為了避免樣本輸出中出現大量數字。

public class App {
   public static void main(String[] args) throws IOException {
       CyclicGroup cg = new CyclicGroup(4);

       System.out.println("Modulus (p): " + cg.getModulus());
       System.out.println("Generator (g): " + cg.getGenerator());
       System.out.println(cg.getElements());
       System.out.println("Random element in group: " + cg.getRandomElement());
   }
}

模數（p）：23

發電機（g）：9

$$ 9, 12, 16, 6, 8, 3, 4, 13, 2, 18, 1 $$ 組內隨機元素：9

**綜上所述，如何確保生成的循環組的順序是素數？**在上面的範例輸出中，我很幸運它的順序是 11。能夠在不計算所有組的元素然後計算它們的情況下做出決定也很好。

我感謝您在這方面能給我的任何幫助。供您參考，我在群論方面的背景充其量是有限的。提前致謝。

如果您正在使用乘法組，則可以使用一種方法 $ Z^*_p $ , 是選擇一個素數 $ p $ 以便 $ p-1 $ 有一個很大的素因數 $ q $ ; 一旦你有了這個，然後生成一個訂單生成器 $ q $ ，你選擇一個隨機值 $ h $ , 計算 $ g = h^{(p-1)/q} $ ，如果不是 1，那麼 $ g $ 是您組的生成器。

明顯的問題：

• 你如何找到一個大的主要因素 $ q $ ， 鑑於 $ p-1 $ 很難考慮？好吧，你選擇主要因素 $ q $ 首先，你尋找一個素數 $ p $ 在表格中 $ kq+1 $ .
• 有多大可能 $ h^{(p-1)/q} \ne 1 $ ? 好吧，如果 $ h $ 從範圍中隨機選擇 $ [1, p-1] $ ，那將是一個有機率的 $ 1/q $ ，所以你幾乎總能得到一個可用的 $ g $ 只有一個隨機 $ h $ .

另一種方法是選擇一個素數 $ p $ 和 $ q = (p-1)/2 $ 也是素數和 $ p \equiv 7 \pmod{8} $ . 在這種情況下， $ g=2 $ 保證是訂單的生成器 $ q $ . 這需要做更多的工作，但是您可以使用素數 $ p $ 來自這個 RFC；所有這些素數都有這些性質。

引用自：https://crypto.stackexchange.com/questions/22716