原始根電卓

原始根電卓へようこそ。これは、任意の正の整数 n に対するすべての原始根を検索する強力な無料オンラインツールです。この電卓は、ステップバイステップの検証、べき乗表、およびアニメーション付きの巡回群可視化を提供し、原始根がどのように乗法群を生成するかを理解するのに役立ちます。数論の学習、暗号技術の試験対策、または競技プログラミングでの剰余演算など、どのような用途でも、教育的な洞察とともに即座に正確な結果を提供します。

原始根とは何ですか？

法 n に対する原始根とは、そのべき乗が n と互いに素なすべての整数を生成するような整数 g のことです。形式的には、法 n における g の乗法位数がオイラーのファイ関数 \(\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 は原始根である

この方法は、すべてのべき乗を計算するよりもはるかに高速です。なぜなら、\(\varphi(n)\) 回ではなく \(k\) 回の累乗計算をテストするだけで済むからです。

暗号技術における原始根

ディフィー・ヘルマン鍵共有

ディフィー・ヘルマンプロトコルでは、大きな素数 p と法 p に対する原始根 g が使用されます。アリスは秘密の値 a を選び、\(g^a \bmod p\) を送信します。ボブは秘密の値 b を選び、\(g^b \bmod p\) を送信します。両者は共有秘密 \(g^{ab} \bmod p\) を計算できます。安全性は、離散対数問題の計算が困難であることに依存しています。

エルガマル暗号

エルガマル暗号もまた、生成元として原始根を使用します。公開鍵は \((p, g, g^x \bmod p)\) で、ここで x は秘密鍵です。g がすべての要素を生成するという事実が、すべてのメッセージを暗号化できることを保証します。

電子署名

DSA (Digital Signature Algorithm) や関連するスキームでは、電子署名の作成と検証のために \((\mathbb{Z}/p\mathbb{Z})^*\) の部分群における原始根が使用されます。

参照表：最小の原始根

よくある質問

法 n に対する原始根とは何ですか？

法 n に対する原始根とは、法 n において \(g^1, g^2, \ldots, g^{\varphi(n)}\) のべき乗が n と互いに素なすべての整数を生成するような整数 g です。言い換えれば、g は乗法群 \((\mathbb{Z}/n\mathbb{Z})^*\) 全体を生成します。法 n における g の乗法位数は、オイラーのファイ関数 \(\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 つ存在します。

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

原始根は、ディフィー・ヘルマン鍵共有プロトコルやエルガマル暗号系の基礎となっています。これらの暗号プロトコルでは、大きな素数 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 のすべてのべき乗を計算するよりもはるかに高速です。

関連ツール