1

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

ax + by = gcd(a,b)

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

4

2 に答える 2

3

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

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

于 2013-01-17T14:54:43.103 に答える
1

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

于 2013-01-18T01:07:36.897 に答える