模 p 的所有生成器
所以我必須找到模 p 的所有生成器。我想：難道沒有規則嗎？據我所知，{1,…,p-1} 中的每個數字都是生成器，因為 p 是素數。真的嗎？還是我弄錯了？規則叫什麼？
或者您如何快速找到生成器元素？你真的需要把每一個元素都用 p 取模，然後確定它是否返回所有數字 n 為 0 > n < p-1 嗎？
所以我必須找到模 p 的所有生成器
嗯，有 $ \phi(p-1) = \Omega( p / \log \log p ) $ 其中
$$ 1 $$; 除非 $ p $ 很小，這是不可行的（因為列出的太多了）。所以，我們假設 $ p $ 相當小（例如數千或數百萬）。 我們有一個三步過程。
- 第 1 步：因素 $ p-1 $ ; 這將是一個素數列表 $ q_0, q_1, …, q_n $ （如果任何素數出現不止一次，您可以忽略第二次和以後的出現）。因為我們假設 $ p $ 相當小，這很容易。
- 第二步：找一個發電機。一種方法是選擇一個隨機值 $ g $ 介於 2 和 $ p-2 $ ; 並檢查是否 $ g^{(p-1)/q_i} \ne 1 \pmod p $ ; 如果對於列表中的所有素數都是如此，那麼 $ g $ 是一個發電機。如果 $ g $ 原來不是另一個發電機，回去再選一個 $ g $ . 由於生成器相當普遍，這不應該花費太長時間。
- 第 3 步：找到所有其他生成器。您無需重複上述過程即可找到其他生成器；相反，通過值 $ 1 < x < p-1 $ 相對質數 $ p-1 $ , 併計算 $ g_x = g^x \bmod p $ ; 每一個這樣的 $ g_x $ 將是另一個發電機。而且，如果你經歷了所有 $ x $ 相對質數的值 $ p-1 $ ，這將得到所有這些。
作為這三個步驟的範例，讓我們考慮 $ p=31 $ .
步驟1： $ p-1 = 2 \times 3 \times 5 $
第2步：我們首先選擇 $ g=26 $ . 有了這個，我們計算 $ g^{30/2} = 30 $ ，那不是 1。然後我們計算 $ g^{30/3} = 5 $ ，那不是一個。然後我們計算 $ g^{30/5} = 1 $ ; 因為那是1，我們拒絕那個 $ g $ 並嘗試另一個。
然後我們挑選 $ g=17 $ . 我們有 $ g^{30/2} = 30 $ , $ g^{30/3}=25 $ 和 $ g^{30/5} = 8 $ ，所以 17 是一個生成器。
第 3 步：範圍內有 8 個整數 $ [1, 30] $ 與 30 互質，即 $ 1, 7, 11, 13, 17, 19, 23 $ 和 $ 29 $ . 因此，這 8 個生成器是 $ 17^1 = 17, 17^7 = 12, 17^{11} = 22, 17^{13} = 3, 17^{17}=21, 17^{19} = 24, 17^{23} = 13 $ 和 $ 17^{29} = 11 $
看，相當直截了當…
$$ 1 $$: 符號 $ f(x) = \Omega( g(x) ) $ 意思是 $ f(x) $ 至少增長得一樣快 $ g(x) $ . 形式上，存在一個 $ m $ 這樣 $ f(x) > m \cdot g(x) $ 總是正確的（對於足夠大的 $ x $ ); 那是， $ f(x) $ 永遠不會低於 $ g(x) $ . 它恰好類似於 $ O() $ 符號，除了它給出了一個下限（“永遠不會小得多”），而不是一個上限（“永遠不會大得多”）