怎麼可能Gq≡1（模組p)Gq≡1(反對p)g^q equiv 1 pmod p對於發電機 g？
這個問題的上下文是 ElGamal 加密方案的參數。
ElGamal 的參數要求之一是我們有素數 $ p $ 和 $ q $ 這樣 $ p = q \cdot k + 1 $ 對於一些 $ k $ . 為簡單起見，讓 $ k=2 $ . 我們還需要一個生成器 $ g $ 為了 $ p $ 這樣 $ g^q \equiv 1 \pmod p $ . （如果我有任何錯誤，請隨時糾正我）。
但是，根據Crypto SE對*“如何測試一個數字是否是原根？”的回答。*， 一個號碼 $ g $ 是一個生成器 $ p $ 當且當 $ g^{\varphi(p)/j} \not \equiv 1 \pmod p $ 對於所有主要因素 $ j $ 的 $ \varphi(p) $ . 自從 $ \varphi(p) = p-1 $ （作為 $ p $ 是素數）和 $ p-1 $ 只有兩個質因數， $ 2 $ 和 $ q $ ， 我們有 $ g^q \not\equiv 1 \pmod p $ .
這不直接與ElGamal的上述要求相矛盾嗎？
對於現實世界的範例，以RFC 2409 中的 IKE 組 1 和 2為例。對於第 2 組，我們有 $ p = $ 一些大素數和 $ (p-1)/2 $ 也等於一些大素數。他們給了我們發電機 $ g=2 $ . 這檢查了 ElGamal，因為 $ 2^p \equiv 1 \pmod p $ . 我還用我的 ElGamal 加密實現對其進行了測試，一切正常。但是，這不與生成器的定義相矛盾嗎？如果我試圖找到一個發電機 $ p $ ，我得到的第一個是 $ g=11 $ ， 因為 $ 11^q \not\equiv 1 \pmod p $ 和 $ 11^2 \not\equiv 1 \pmod p $ . 但是如果我使用 $ g=11 $ ，加密失敗，因為據我所知， $ 11^q \not\equiv 1 \pmod p $ .
您可能對這裡的“生成器”的含義感到困惑。您是正確的，整個乘法組模的生成器 $ p $ 不能滿足 $ g^q \equiv 1 $ 根據定義。
但是 - 假設 $ k = 2 $ 在這裡-您可能讀到的是 $ g $ 是二次餘數模的生成器 $ p $ , 這個組有順序 $ (p - 1)/2 $ . 發電機 $ g $ 因為那個群顯然是一個二次餘數，這意味著它的形式是 $ g = a^2 \pmod{p} $ 對於某些組元素 $ a $ ，因此必須滿足 $ g^q \equiv 1 \pmod{p} $ ， 自從 $ g^q = (a^2)^q = a^{2q} = a^{p - 1} $ .
這樣就清楚了嗎？