Modular Linear Equation
合同線形方程式ax≡b (mod n)を解く。解が存在するのはgcd(a,n)がbを割り切るときであり、そのとき解はちょうどgcd(a,n)個存在する。
目的
合同方程式を解き、モジュラ演算のもとでいつ除算が可能かを理解する。
メカニズム
d=gcd(a,n)とおく。dがbを割り切らなければ解は存在しない。割り切れる場合は、拡張ユークリッドの互除法で(a/d)·x0 ≡ b/d (mod n/d)の一意解を求め、すべての解はk=0..d-1に対するx0 + k*(n/d) mod nとなる。
ユースケース
- 暗号での方程式求解（equation solving）
- モジュラ演算
- 数論に基づく数値計算（number theory）