原始根電卓

原始根電卓

原始根計算機は、与えられた法 n に対するすべての原始根を見つけます。原始根とは、べき乗 \(g^1, g^2, \ldots, g^{\varphi(n)}\) が乗法群 \((\mathbb{Z}/n\mathbb{Z})^*\) のすべての要素を生成するような整数 g です。任意の正の整数を入力すると、すべての原始根、オイラーのトーシェント \(\varphi(n)\)、インタラクティブな巡回群のビジュアライゼーション、べき乗表、および最小の原始根のステップごとの検証が即座に表示されます。

原始根の応用

主要な概念と公式

原始根の理解

法 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))\) 個の原始根が存在することになります。

原始根電卓の使い方

1. 法 n を入力する: 入力フィールドに正の整数を入力するか、クイック例ボタンのいずれかをクリックして値を自動入力します。
2. 「原始根を見つける」をクリック: ボタンを押して、法 n に対するすべての原始根を計算します。
3. 結果を確認する: 個数、原始根の完全なリスト、オイラーのトーシェント、群の位数、および入力した n に原始根が存在するかどうかを確認します。
4. ビジュアライゼーションを探索する: n ≤ 100 の場合、インタラクティブな巡回群ホイールにより、各原始根がそのべき乗を通じてどのように群全体を生成するかを確認できます。根のチップをクリックすると、そのサイクルがホイール上でアニメーション表示されます。
5. べき乗表を調べる: グリッドには 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)

高度な数学操作:

• antilog電卓
• ベータ関数電卓
• 二項係数電卓 おすすめ
• 二項確率分布電卓
• ビットに基づいての電卓
• 中心極限定理電卓
• 組み合わせ電卓
• 相補誤差関数電卓
• 複素数電卓
• エントロピー電卓
• エラー関数電卓 おすすめ
• 指数減衰電卓-高精度
• 指数成長電卓 高精度
• 指数積分電卓
• 指数電卓-高精度 おすすめ
• 階乗電卓
• ガンマ関数電卓
• 黄金比電卓
• 半減期電卓
• パーセント成長率電卓 おすすめ
• 順列電卓
• ポアソン分布電卓
• 多項式の根電卓と詳細なステップ
• 確率電卓
• 確率分布電卓
• 比率電卓
• 二次式電卓
• 関数電卓 おすすめ
• 科学表記法電卓
• 有効数字電卓 新しい
• 立方和電卓
• 正の整数の電卓
• 平方和の計算
• 真理値表ジェネレーター
• 集合論電卓
• ベン図ジェネレーター3集合
• 中国剰余定理電卓 おすすめ
• オイラーのトーシェント関数電卓
• 拡張ユークリッドアルゴリズム電卓
• モジュラー乗法逆数電卓
• 連分数電卓
• ダイクストラ最短経路電卓
• 最小全域木電卓
• グラフ次数列バリデーター
• 完全順列 サブファクトリアル電卓
• スターリング数電卓
• 鳩の巣原理電卓
• マルコフ連鎖定常分布電卓 おすすめ
• 四捨五入電卓 新しい
• 負の二項分布電卓 新しい
• 重複順列電卓 新しい
• モジュラー冪乗計算機 新しい
• 原始根電卓
• ブール代数簡略化ツール 新しい
• カルノー図 (K-Map) ソルバー 新しい
• グラフ彩色電卓 新しい
• トポロジカルソート電卓 新しい
• 隣接行列電卓 新しい
• 包除原理電卓 新しい
• 線形計画法ソルバー 新しい
• 巡回セールスマン問題ソルバー TSP 新しい
• ハミルトン路チェッカー 新しい
• 平面グラフ判定 新しい
• ネットワークフロー電卓最大フロー 新しい
• 安定結婚問題ソルバー 新しい
• 群論の位数電卓 新しい
• 環と体の電卓 新しい