mod b を指定してその逆数を見つけ、拡張 GCD を実行します。
ax + by = gcd(a,b)
x と y を取得した後、その逆数を取得するにはどうすればよいですか?
mod b を指定してその逆数を見つけ、拡張 GCD を実行します。
ax + by = gcd(a,b)
x と y を取得した後、その逆数を取得するにはどうすればよいですか?
の場合gcd(a,b) != 1
、a
逆 はありませんmod b
。
それ以外ax + by = 1
の場合はax = 1 (mod b)
、modx
の逆になります。a
b
モジュラスmに対するxの逆数を計算するには、次のようにします。
function inverse(x, m)
a, b, u := 0, m, 1
while x > 0
q, r := divide(b, x)
x, a, b, u := b % x, u, x, a - q * u
if b === 1 return a % m
error("must be coprime")
:=
これは同時代入演算子なので、右側のすべての計算が最初に行われ、次にすべての代入が行われます。このdivide
関数は、 の商と剰余の両方を返しますb / x
。