原根計算機

歡迎使用原根計算機，這是一個功能強大的免費線上工具，可以尋找任何正整數 n 的所有原根。本計算機提供逐步驗證、乘方表以及動畫循環群視覺化，幫助您了解原根如何生成乘法群。無論您是在學習數論、準備密碼學考試，還是在競賽程式設計中處理模運算，本工具都能提供即時、準確的結果與教育見解。

什麼是原根？

模 n 的原根是一個整數 g，其乘方可以生成所有與 n 互質的整數。正式地說，如果 g 模 n 的乘法階等於歐拉函數 \(\varphi(n)\)，則 g 是模 n 的原根。這意味著集合

恰好包含從 1 到 n-1 中所有與 n 互質的 \(\varphi(n)\) 個整數。原根本質上是循環群 \((\mathbb{Z}/n\mathbb{Z})^*\) 的生成元。

快速示例

考慮 n = 7。由於 7 是質數，\(\varphi(7) = 6\)。讓我們檢查 g = 3 是否為原根：

• 3¹ mod 7 = 3
• 3² mod 7 = 2
• 3³ mod 7 = 6
• 3⁴ mod 7 = 4
• 3⁵ mod 7 = 5
• 3⁶ mod 7 = 1

乘方產生的集合為 {3, 2, 6, 4, 5, 1} = {1, 2, 3, 4, 5, 6}，這是所有與 7 互質的整數。因此 3 是模 7 的一個原根。

何時存在原根？

模 n 存在原根若且唯若 n 為以下形式之一：

• n = 1, 2, 或 4
• n = p^k，其中 p 是奇質數且 k ≥ 1
• n = 2p^k，其中 p 是奇質數且 k ≥ 1

例如，對於 7, 9, 11, 13, 14, 18, 23, 25, 27, 46 存在原根，但對於 8, 12, 15, 16, 20, 21, 24 則不存在。

如何尋找原根

1. 輸入模數： 在輸入欄位中輸入一個正整數 n（從 2 到 100,000）。
2. 計算： 點擊「尋找原根」或按下 Enter 鍵。
3. 查看所有原根： 查看完整的原根列表，以及歐拉函數和統計數據。
4. 研究乘方表： 觀察最小原根如何生成所有互質餘數。
5. 視覺化循環群： 對於較小的模數，可以查看顯示循環結構的動畫輪盤。

n 有多少個原根？

如果模 n 存在原根，其數量等於：

例如，對於 n = 13：\(\varphi(13) = 12\) 且 \(\varphi(12) = 4\)，因此模 13 恰好有 4 個原根（分別是 2, 6, 7, 11）。

驗證演算法

要有效率地檢查 g 是否為模 n 的原根：

1. 使用 n 的質因數分解計算 \(\varphi(n)\)
2. 找出 \(\varphi(n)\) 的所有相異質因數 \(p_1, p_2, \ldots, p_k\)
3. 對於每個質因數 \(p_i\)，檢查：\(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\)
4. 如果所有檢查都通過，則 g 是原根

這種方法比計算 g 的所有乘方要快得多，因為我們只需要測試 \(k\) 次冪運算，而不是 \(\varphi(n)\) 次。

密碼學中的原根

Diffie-Hellman 金鑰交換

Diffie-Hellman 協定使用一個大質數 p 和一個模 p 的原根 g。Alice 選擇秘密 a，發送 \(g^a \bmod p\)。Bob 選擇秘密 b，發送 \(g^b \bmod p\)。雙方計算共享秘密 \(g^{ab} \bmod p\)。安全性依賴於計算離散對數問題的困難性。

ElGamal 加密

ElGamal 同樣使用原根作為生成元。公鑰為 \((p, g, g^x \bmod p)\)，其中 x 是私鑰。g 生成所有元素的事實確保了每條訊息都可以被加密。

數位簽章

DSA（數位簽章演算法）及相關方案在 \((\mathbb{Z}/p\mathbb{Z})^*\) 的子群中使用原根來創建和驗證數位簽章。

參考表：最小原根

常見問題解答

什麼是模 n 的原根？

模 n 的原根是一個整數 g，使得乘方 \(g^1, g^2, \ldots, g^{\varphi(n)}\) 在模 n 下產生所有與 n 互質的整數。換句話說，g 生成了整個乘法群 \((\mathbb{Z}/n\mathbb{Z})^*\)。g 模 n 的乘法階等於歐拉函數 \(\varphi(n)\)。

對於哪些 n 值存在原根？

模 n 存在原根若且唯若 n 為 1, 2, 4, p^k 或 2p^k，其中 p 是奇質數且 k ≥ 1。例如，對於 n = 7（質數）、n = 9 (3²)、n = 14 (2×7) 存在原根，但對於 n = 8, 12, 15 或 16 則不存在。

n 有多少個原根？

如果模 n 存在原根，原根的數量等於 \(\varphi(\varphi(n))\)，其中 \(\varphi\) 是歐拉函數。例如，對於 n = 13（質數），\(\varphi(13) = 12\) 且 \(\varphi(12) = 4\)，因此模 13 恰好有 4 個原根。

為什麼原根在密碼學中很重要？

原根是 Diffie-Hellman 金鑰交換協定和 ElGamal 加密系統的基礎。在這些加密協定中，模大質數 p 的原根 g 被用作生成元。安全性依賴於離散對數問題的難度：給定 \(g^x \bmod p\)，在計算上很難找到 x。

如何驗證 g 是否為模 n 的原根？

要驗證 g 是否為模 n 的原根：(1) 計算 \(\varphi(n)\)。(2) 找出 \(\varphi(n)\) 的所有質因數 \(p_1, p_2, \ldots, p_k\)。(3) 檢查對於每個質因數 \(p_i\)，\(g^{\varphi(n)/p_i} \not\equiv 1 \pmod{n}\) 是否成立。如果所有檢查都通過，則 g 是原根。這比計算 g 的所有乘方要快得多。

相關工具