algorithm - モジュラー逆数

Question

最近私は拡張されたユークリッドのアルゴリズムを読みました。これは、そのようなNに関する数値の剰余逆数を見つけるために使用されます。MODgcd(N,MOD)=1

しかし、次の場合にモジュラー逆数を見つける方法については疑問がありgcd(N,MOD)!=1ます。

Answer 1

gcd(N,MOD)!=1N の剰余逆数が存在しない場合。

ただし、N で割ることができる場合もあります。つまり、A = N * X (mod MOD) となる X を見つけることができます。これは、gcd(N,MOD) が gcd(A,MOD) を割るときに可能です。このような X を見つけるには、A、N、および MOD を gcd(N,MOD) で割り、通常どおりに処理します (gcd(N', MOD') は 1 です)。