原根計算機

尋找給定模數 n 的所有原根 — 乘法群 (Z/nZ)* 的生成元。輸入任何正整數以獲取原根、Euler's totient（歐拉函數）、循環群視覺化以及使用乘方表的逐步驗證。

原根計算機

本「原根計算機」用於尋找給定模數 n 的所有原根 — 即滿足其冪次 \(g^1, g^2, \ldots, g^{\varphi(n)}\) 能生成乘法群 \((\mathbb{Z}/n\mathbb{Z})^*\) 中每個元素的整數 g。輸入任何正整數即可立即查看所有原根、歐拉函數 \(\varphi(n)\)、互動式循環群視覺化圖表、冪次表以及最小原根的逐步驗證過程。

原根的應用

🔐

Diffie-Hellman

金鑰交換協定使用原根作為生成元

🔏

ElGamal 加密

基於離散對數的公鑰加密系統

✍

數位簽章

DSA 和 Schnorr 簽章依賴循環群生成元

🎲

偽隨機數

線性同餘生成器利用原根特性

📡

糾錯碼

Reed-Solomon 和 BCH 碼使用有限體生成元

🧮

數論

指數運算、二次剩餘和離散對數問題

關鍵概念與公式

概念	公式 / 定義	說明
原根	\(\text{ord}_n(g) = \varphi(n)\)	階數 mod n 等於歐拉函數的整數 g
歐拉函數	\(\varphi(n) = n \prod_{p\|n}\left(1 - \frac{1}{p}\right)\)	[1, n] 中與 n 互質的整數個數
存在性準則	\(n \in \{1, 2, 4, p^k, 2p^k\}\)	原根僅存在於這些形式（p 為奇質數）
原根數量	\(\varphi(\varphi(n))\)	當原根存在時的總個數
原根測試	對於所有質因數 \(p \| \varphi(n)\)，\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\)	充分條件：僅需檢查 φ(n) 的質因數
生成所有根	\(g^k \bmod n\)，其中 \(\gcd(k, \varphi(n)) = 1\)	一旦找到一個原根 g，其餘即可求得

理解原根

模 n 的原根是一個整數 g，使得集合 \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) 等於 1 到 n−1 之間所有與 n 互質的整數集合。在群論術語中，g 是循環乘法群 \((\mathbb{Z}/n\mathbb{Z})^*\) 的生成元。例如，3 是模 7 的一個原根，因為其冪次 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1 (mod 7) 產生了集合 {1, 2, 3, 4, 5, 6} 中的每個元素。

原根何時存在？

數論中的一個經典結果（由高斯證明）指出，模 n 的原根存在的充要條件是 n 為：1, 2, 4, p^k 或 2p^k，其中 p 是奇質數且 k ≥ 1。對於 n 的其他值，群 \((\mathbb{Z}/n\mathbb{Z})^*\) 不是循環群 — 根據中國剩餘定理，它可以分解為循環群的直積 — 因此沒有單個元素可以生成整個群。例如，\((\mathbb{Z}/8\mathbb{Z})^* \cong \mathbb{Z}/2 \times \mathbb{Z}/2\) 就沒有原根。

如何高效尋找原根

標準演算法分為兩個階段。第一階段：透過嘗試法尋找最小原根。對於從 2 開始的每個候選數 g，計算 \(\varphi(n)\) 的每個質因數 p 的 \(g^{\varphi(n)/p} \bmod n\)。如果這些結果都不等於 1，則 g 就是原根。在實務中，最小原根通常很小 — 據猜想對於任何 \(\epsilon > 0\)，其數量級為 \(O(n^\epsilon)\)。第二階段：一旦已知一個原根 g，所有其他原根均為 \(g^k \bmod n\)，其中 \(\gcd(k, \varphi(n)) = 1\)，總共恰好有 \(\varphi(\varphi(n))\) 個原根。

如何使用原根計算機

輸入模數 n：在輸入欄位中輸入一個正整數，或點擊快速範例按鈕自動填充數值。
點擊尋找原根：按下按鈕計算模 n 的所有原根。
查看結果：查看數量、完整的原根列表、歐拉函數、群階，以及您的 n 是否存在原根。
探索視覺化圖表：對於 n ≤ 100，互動式循環群輪狀圖顯示每個原根如何透過其冪次生成整個群。點擊任何根值晶片即可在輪狀圖上查看其循環動畫。
研究冪次表：表格顯示 k = 1, 2, …, φ(n) 的 g^k mod n，其中原根和單位元以不同的顏色突顯。

密碼學中的原根

原根在現代密碼學中扮演著核心角色。在 Diffie-Hellman 金鑰交換中，通訊雙方約定一個大質數 p 和一個模 p 的原根 g，然後交換公鑰 g^a mod p 和 g^b mod p。共享密鑰 g^ab mod p 對於竊聽者來說在計算上是不可行的，因為在大型循環群中計算離散對數被認為是非常困難的。同樣，ElGamal 加密和數位簽章演算法 (DSA) 都依賴於原根所生成的群中離散對數問題的難度。

FAQ

什麼是模 n 的原根？

模 n 的原根是一個整數 g，使得冪次 g¹, g², …, g^φ(n) 模 n 剛好產生每個與 n 互質的整數各一次。等價地，g 的乘法階等於 φ(n)，這意味著 g 生成了整個乘法群 (Z/nZ)*。

對於哪些 n 值存在原根？

原根存在的充要條件是 n 為 1, 2, 4, p^k 或 2p^k，其中 p 是奇質數且 k 是正整數。例如，n = 7（質數）、n = 9 (3²) 和 n = 14 (2 × 7) 都有原根，但 n = 8, n = 12 和 n = 15 則沒有。

n 有多少個原根？

如果 n 存在原根，那麼模 n 的原根數量等於 φ(φ(n))，其中 φ 是歐拉函數。例如，n = 7 有 φ(φ(7)) = φ(6) = 2 個原根，分別是 3 和 5。

如何找到原根？

尋找 n 的原根：首先計算 φ(n) 並進行質因數分解。然後對於每個與 n 互質的候選數 g，檢查對於 φ(n) 的每個質因數 p，g^(φ(n)/p) 是否不模 n 同餘於 1。如果所有檢查都通過，則 g 是一個原根。其他所有原根可以表示為 g^k mod n，其中 gcd(k, φ(n)) = 1。

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

原根是 Diffie-Hellman 金鑰交換、ElGamal 加密和數位簽章演算法的基礎。它們確保了離散對數問題的難度，這是這些加密協定安全性的基礎。原根生成群的所有元素，最大限度地增加了攻擊者的搜尋空間。

引用此內容、頁面或工具為：

"原根計算機" 於 https://MiniWebtool.com/zh-tw/原根計算機/，來自 MiniWebtool，https://MiniWebtool.com/

由 MiniWebtool 團隊製作。更新日期：2026-04-16

您還可以嘗試我們的 AI數學解題器 GPT，通過自然語言問答解決您的數學問題。

其他相關工具:

原根計算機