Fotools
EN

合同式解法ツール

パラメータ入力

クイック例：

計算結果

パラメータを入力して「方程式を解く」をクリック

アルゴリズム説明：

1. 線形合同式 ax ≡ b (mod m)：
  • 解の存在条件：gcd(a, m) | b（b が gcd(a, m) で割り切れる）ときのみ解が存在
  • 解の個数：解がある場合、法 m のもとで d = gcd(a, m) 個の異なる解が存在
  • 解法手順：
    1. d = gcd(a, m) を計算
    2. d | b を確認、満たさなければ解なし
    3. 方程式の両辺を d で割る：(a/d)x ≡ (b/d) (mod m/d)
    4. 拡張ユークリッドの互除法で a/d の法 m/d における逆元 a' を求める
    5. x₀ = a' × (b/d) mod (m/d) を計算
    6. 一般解：x = x₀ + k(m/d)、k = 0, 1, ..., d-1
2. 指数合同式 a^x ≡ b (mod m)（離散対数問題）：
  • 問題の説明：a, b, m が与えられたとき、a^x ≡ b (mod m) となる最小の非負整数 x を求める
  • 解の存在条件：
    • gcd(a, m) = 1 かつ b が a の生成する法 m 上の巡回群の元であれば解が存在
    • 確認方法：a のべき乗を列挙し、b が見つかるか1周期を終えるまで繰り返す
  • 解法手順：
    • 小範囲での全探索：x = 0, 1, 2, ... と列挙し、解が見つかるか上限に達するまで繰り返す
    • Baby-step Giant-step アルゴリズム：時間計算量 O(√m)、中規模の問題に適用
    • Pollard's rho アルゴリズム：大きな素数の法に適用
  • 周期性：x₀ が解ならば、x = x₀ + kφ(m) も解（φ(m) はオイラーのトーシェント関数）
3. 応用シーン：
  • 暗号理論：RSA、Diffie-Hellman 鍵交換、ElGamal 暗号
  • 数論研究：原始根、平方剰余、中国剰余定理
  • 乱数生成：線形合同法（LCG）
  • ハッシュ関数：ハッシュテーブルにおける剰余演算の応用
  • 競技プログラミング：繰り返し二乗法、モジュラ逆数、数論問題

アルゴリズムの計算量：

  • 線形合同式：O(log m)（拡張ユークリッドの互除法の計算量）
  • 指数合同式（全探索）：O(n)、n は探索上限
  • 指数合同式（BSGS）：O(√m)、追加のメモリが必要

重要な定理：

  • ベズーの定理：方程式 ax + my = gcd(a, m) は常に整数解を持つ
  • フェルマーの小定理：p が素数で gcd(a, p) = 1 ならば、a^(p-1) ≡ 1 (mod p)
  • オイラーの定理：gcd(a, m) = 1 ならば、a^φ(m) ≡ 1 (mod m)
  • 中国剰余定理：連立合同式を解くことができる