拡張ユークリッドの互除法を使う
拡張 GCD は ax + by = gcd(a, b) を満たす x, y を求めます。モジュラ逆数と中国剰余定理に不可欠です。
- 1
拡張ユークリッドの互除法は gcd(a, b) を計算すると同時に、a*x + b*y = gcd(a, b) を満たすベズー係数 x、y を求めます。gcd(a, b) = 1 であれば、x は a の b を法とするモジュラ逆数になります (a*x ≡ 1 mod b)。このアルゴリズムは RSA (d = e^(-1) mod φ(n))、CRT、および線形ディオファントス方程式の求解に使われます。
- 2 最大公約数計算ツール →
GCD とベズー係数を計算します。a と b を入力すると、ツールは a*x + b*y = gcd を満たす gcd(a,b)、x、y を返します。検証：gcd = 1 であれば、x mod b が a の b を法とするモジュラ逆数です。
- 3 剰余逆元計算ツール →
モジュラ逆数を直接計算します。a と m が与えられたとき、a * a^(-1) ≡ 1 mod m を満たす a^(-1) mod m を求めます。逆数が存在するのは、gcd(a, m) = 1 のとき、かつそのときに限ります。この計算は内部的に拡張 GCD を利用しています。
よくある質問
- モジュラ逆数はいつ存在しますか？
- a が m を法とする逆数を持つのは、gcd(a, m) = 1 (a と m が互いに素) のとき、かつそのときに限ります。gcd(a, m) > 1 なら逆数は存在しません。m が素数のときは、0 以外のすべての要素が逆数を持ちます。m が合成数のときは、m と互いに素な要素だけが逆数を持ち、その数は φ(m) 個です。
- 拡張 GCD は RSA でどのように使われますか？
- RSA の鍵生成では、e (公開指数、通常は 65537) を選び、d = e^(-1) mod φ(n) (ここで φ(n) = (p-1)(q-1)) を計算します。d は秘密指数で、拡張 GCD を使って計算します。e*d + φ(n)*k = 1 を満たす d と k を求め、その d mod φ(n) が秘密鍵になります。