有效地找到乘法組的生成器？
假設你要給出一些素數 $ p_{1},p_{2},p_{3}, p = 2p_{1}p_{2}p_{3} + 1 $ （假設也是素數）和一個數字列表 $ L $ 並且你被要求找到乘法組的生成器 $ Z_p $ .
什麼是這樣做的有效方法？
這個問題來自密碼學課程，所以素數真的很大，而且數字列表是由大數字組成的，所以我很難應用這種方法。
對於任何 $ g $ 在集合中 $ \mathbb Z_p^*={1,2,\dots,p-1} $ , 考慮函式 $ F_g $ 在由定義的集合上 $ F_g(x);=;g\cdot x\bmod p $ . 自從 $ p $ 是素數，根據費馬小定理，迭代 $ F_g $ ， 從…開始 $ 1 $ , $ p-1 $ 次，循環回到 $ 1 $ .
根據定義， $ g $ 是一個生成器 $ \mathbb Z_p^* $ 當且僅當在這些之前沒有發生該循環 $ p-1 $ 迭代。最小的 $ k>0 $ 發生循環的地方分為 $ p-1 $ （那 $ k $ 是順序 $ g $ ）。證明草圖：如果那樣 $ k $ 沒有分 $ p-1 $ , $ k’=(p-1)\bmod k $ 會更小 $ k’>0 $ 發生循環的。
因此，我們可以測試是否有一些 $ g $ 不能被 $ p $ 是一個生成器 $ \mathbb Z_p^* $ 通過檢查是否 $ g^k\bmod p\ne1 $ ， 和 $ k=(p-1)/q $ 為了 $ q $ 每個不同的質因數 $ p-1 $ .
在這裡，對於 $ g $ 列表中的每個整數 $ L $ , 我們檢查是否 $ g\bmod p\ne0 $ ， 和 $ g^{(p-1)/2}\bmod p\ne1 $ ， 和 $ g^{(p-1)/p_1}\bmod p\ne1 $ ， 和 $ g^{(p-1)/p_2}\bmod p\ne1 $ ， 和 $ g^{(p-1)/p_3}\bmod p\ne1 $ . 在肯定的情況下，只有這樣， $ g $ 是一個生成器 $ \mathbb Z_p^* $ .
補充：
- 計算 $ g^k\bmod p $ 對於數千位的整數來說，在一台普通的電腦上是可行的，並且很常見： $ 2\log_2(k) $ 模乘足以計算 $ g^k\bmod p $ ; 請參閱模冪運算。
- 如果列表 $ L $ 不是給定的，我們可以嘗試 $ g $ 隨機（或通過增加順序來增加小素數，這比通過增加順序嘗試小整數稍微更有效）。如果所有素數除 $ (p-1)/2 $ 很大（這裡就是這種情況），將近 50% 的候選人會工作，因此搜尋不會太長。
- 通常，我們想要一個大素數除法的子群的生成器 $ p-1 $ ， 說 $ p_3 $ ; 我們可以得到 $ g’=g^{(p-1)/p_3}\bmod p $ .