オンライン離散対数ソルバー

離散対数とは

離散対数とは、合同式 g^x ≡ h (mod p) において、与えられた g, h, p に対して x を求める問題です。このツールは、x を 0 から p-1 まで順に調べる総当たり方式で解を探索します。

具体的な計算例

デフォルトの入力 g=2, h=8, p=13 の場合、2^3 = 8 なので、2^3 mod 13 = 8 となり、x=3 が解として返されます。このように、実際の入出力を確認しながら動作を理解できます。

入力の制約と処理の詳細

g, h, p はすべて整数である必要があります。p は 2 以上 1,000,000 以下に制限されています。h は p で割った余りに正規化されるため、負の値や p 以上の値でも対応します。探索は指数 0 から始まり、毎回 value = (value * g) mod p と更新しながら h と比較します。p 回調べても一致しない場合は解なしと判定します。

法 p が素数である必要はなく、g が生成元であることも保証されません。g と p が互いに素でない場合、数列が短い周期に入ることがありますが、このツールは範囲内を総当たりで調べるため、解があれば最初に見つかった指数を返します。

このツールの用途と限界

このツールは教育目的の O(p) の総当たり探索であり、baby-step giant-step や Pollard rho などの効率的なアルゴリズムは使用していません。また、暗号学的な攻撃を目的としたものではありません。実際の暗号で使われる巨大な法では計算が非現実的です。計算はすべてブラウザ内で行われ、サーバーや AI は使用しません。

重要な用途では、結果を独立に検証することをお勧めします。このツールの出力は、秘密鍵の回復やセキュリティ評価を意味するものではありません。

よくある質問

Q1: 解が見つからない場合はどうなりますか？

p 回の探索で一致する指数が見つからない場合、「解なし」と表示されます。これは、与えられた g, h, p の組み合わせでは解が存在しないことを意味します。

Q2: 負の h を入力できますか？

はい、できます。h は自動的に p で割った余りに正規化されるため、負の値でも対応します。例えば、p=13 のとき h=-5 は h=8 として扱われます。

Q3: 法 p に素数以外を指定できますか？

はい、p は素数である必要はありません。ただし、g と p が互いに素でない場合、数列が短い周期に入る可能性がありますが、総当たり探索により解があれば見つかります。

チェックリスト

• g, h, p が整数であることを確認する
• p が 2 以上 1,000,000 以下であることを確認する
• 計算結果を別の方法で検証する
• 教育目的であることを理解する