自 2010 年 · 每月支援超過 200 萬次工具執行
自 2010 年
加到 Chrome

我的工具箱

自動模式

尚未收藏任何工具。

升級為高級版
相關工具
複數計算機模乘逆元計算機多項式根計算機與詳細步驟環與體計算機群論階數計算機歐拉函數計算機
主頁 > 數學 > 進階數學計算
 

原根計算機

找出模數 n 的所有原根，也就是乘法群的生成元。輸入正整數即可得到原根、歐拉函數值、循環群示意，以及含冪次表的驗證過程。

免費使用無需註冊即時出結果
原根計算機立即免費試用 ▼
範例：
原根存在的條件為 n = 1, 2, 4, pk 或 2pk (p 為奇質數)

Embed 原根計算機 Widget

原根計算機

本「原根計算機」用於尋找給定模數 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, pk 或 2pk，其中 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))\) 個原根。

如何使用原根計算機

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

密碼學中的原根

原根在現代密碼學中扮演著核心角色。在 Diffie-Hellman 金鑰交換中，通訊雙方約定一個大質數 p 和一個模 p 的原根 g，然後交換公鑰 ga mod p 和 gb mod p。共享密鑰 gab 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

開發者 API 可用: 用一次 JSON HTTP 請求，把這個工具接入你的應用程式、自動化流程或代理。 查看 API 文件

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

進階數學計算:

熱門與最新工具:

有理根定理計算機立方根計算機數字根計算機查看全部 →
主頁 > 數學 > 進階數學計算 > 原根計算機