cryptography - 拡張ユークリッド アルゴリズムを使用してモジュラー逆を取得するには?

Question

mod b を指定してその逆数を見つけ、拡張 GCD を実行します。

ax + by = gcd(a,b)

x と y を取得した後、その逆数を取得するにはどうすればよいですか?

Answer 1

の場合gcd(a,b) != 1、a逆 はありませんmod b。

それ以外ax + by = 1の場合はax = 1 (mod b)、modxの逆になります。ab

Answer 2

モジュラス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。