原始根電卓

与えられた法 n のすべての原始根（乗法群 (Z/nZ)* の生成元）を見つけます。正の整数を入力すると、原始根、オイラーの φ 関数、巡回群の視覚化、およびべき乗表によるステップバイステップの検証結果を表示します。

原始根電卓

原始根計算機は、与えられた法 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)\)	法 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))\)	原始根が存在する場合の原始根の数
原始根テスト	\(g^{\varphi(n)/p} \not\equiv 1 \pmod{n}\) （すべての \(p \| \varphi(n)\) に対して）	十分条件：φ(n) の素因数のみをチェックすればよい
全原始根の生成	\(g^k \bmod n\) （\(\gcd(k, \varphi(n)) = 1\) の場合）	一つの根 g が見つかれば、他はすべてそれから導ける

原始根の理解

法 n に対する原始根とは、セット \(\{g^1 \bmod n, g^2 \bmod n, \ldots, g^{\varphi(n)} \bmod n\}\) が 1 から n−1 までの整数の中で n と互いに素なすべての整数の集合と等しくなるような整数 g です。群論の用語では、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 つのフェーズで動作します。フェーズ 1：試行錯誤によって最小の原始根を見つけます。2 から順に候補 g を選び、\(\varphi(n)\) のすべての素因数 p に対して \(g^{\varphi(n)/p} \bmod n\) を計算します。これらが一つも 1 に等しくなければ、g は原始根です。実際、最小の原始根は通常小さく、任意の \(\epsilon > 0\) に対して \(O(n^\epsilon)\) であると予想されています。フェーズ 2：一つの原始根 g が判明すれば、他のすべての原始根は \(\gcd(k, \varphi(n)) = 1\) となる \(g^k \bmod n\) であり、合計で正確に \(\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^φ(n) (mod n) が n と互いに素なすべての整数をちょうど一度ずつ生成するような整数 g のことです。同等に、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 は原始根です。他のすべての根は、gcd(k, φ(n)) = 1 となる g^k mod n として見つけることができます。

暗号技術において原始根が重要なのはなぜですか？

原始根は Diffie-Hellman 鍵交換、ElGamal 暗号、およびデジタル署名アルゴリズムの基礎となっています。これらは離散対数問題の困難さを保証しており、これが暗号プロトコルのセキュリティの根拠となります。原始根は群のすべての要素を生成するため、攻撃者の探索空間を最大化します。

このコンテンツ、ページ、またはツールを引用する場合は、次のようにしてください：

"原始根電卓"（https://MiniWebtool.com/ja/原始根電卓/） MiniWebtool からの引用、https://MiniWebtool.com/

miniwebtool チームによる提供。更新日: 2026-04-16

また、AI 数学ソルバー GPT を使って、自然言語による質問と回答で数学の問題を解決することもできます。