如何找到復合組的生成器和從p∗從p∗Z_p*?
我正在對橢圓曲線進行一些研究。我知道如何找到 $ Z_p $ （這是一個素數組）。但我遇到了這個詞 $ Z_p* $ （包含相對質數的元素的組 $ p $ ，顯然是複合的）。
所以我想知道如何找到復合組的生成器。如何找到*“複合組”的“生成器”（組順序是複合的）？我怎樣才能找到“生成器* $ Z_p $ “*（具有復合元素的欄位範圍為 $ {1,2,\dots,p-1} $ )?
$ \newcommand{\Z}{\mathbb{Z}} $ 如果我正確理解了您的問題，您的目標是找到一個原始根模 $ p $ ，也稱為生成器 $ (\Z/p\Z)^\times $ ， 知道 $ p $ 是素數。
你知道素數分解嗎 $ \phi(p) = p - 1 $ ? 如果你不這樣做，這很難。如果你這樣做了，至少有一個常見的快速案例，並且總是有一個普遍的慢案例。
- 快速案例。是 $ p $ 一個安全的素數——也就是說，是否存在另一個素數 $ q $ 這樣 $ p = 2 q + 1 $ ? 如果是這樣，那麼只有四個可能的順序， $ {1,2,q,2q} $ , 分別對應於子群 $ {1} $ , $ {1, -1} $ ，二次殘差和整個組。因此找到一個生成器 $ (\Z/p\Z)^\times $ 只需找到除 $ -1 $ .
您可以使用二次互易定律快速選擇發電機。例如，如果 $ p \equiv 3 \pmod 8 $ 或者 $ p = 5 $ ， 然後 $ 2 $ 是二次非殘差，因此是生成元；否則 $ p \equiv 7 \pmod 8 $ ， 自從 $ p \equiv 3 \pmod 4 $ 由於是大於 5 的安全素數，所以 $ -2 $ 是二次非殘差，因此是生成元。
（為什麼這種情況很常見？通常的目標是找到一個 Diffie-Hellman 群的生成器，它在有限域上總是使用安全的素數模數完成的——儘管在那種情況下通常會尋找一個階的生成器—— $ q $ 取而代之的是子群，即除 $ -1 $ . 參見，例如，RFC 2412，附錄 E ‘The Well-Known Groups’。）
- 否則，一般情況。讓 $ \phi(p) = p - 1 = q_0^{e_0} q_1^{e_1} \cdots q_{k-1}^{e_{k-1}} $ 對於素數 $ q_i $ . 通過二次非殘差行進 $ x \in (\Z/p\Z)^\times \setminus {-1} $ ，並且對於每個不同的因素 $ q_i $ 的 $ p - 1 $ , 檢查是否$$ x^{\phi(p)/q_i} \equiv 1 \pmod{p}. $$ 如果對於一些 $ x $ 權力 $ x^{\phi(p)/q_i} $ 都不等於1 模 $ p $ ，那麼你找到了一個最大階的元素 $ \phi(p) $ 因此它是一個生成器。
（測試所有元素並沒有什麼壞處，但是您可以比計算模冪更快地跳過二次殘差。）
通常 $ Z_p^* $ 表示有限域的乘法群 $ Z_p = {\mathbb F}_p = {\mathbb Z}/p{\mathbb Z} $ 以素數為模的整數 $ p $ . 眾所周知，域的乘法群的有限子群是循環的，即由單個元素生成。在完全乘法群的情況下 $ Z_p^* $ 這樣的生成器通常被稱為原根，但要找到一種算法，可以證明在給定素數的情況下快速找到原根，這是一個眾所周知的困難（=未解決）問題 $ p $ .
還請查看維基百科。