M を法とする a の逆元

2012-01-27

12:25 |

gcd(M, a)==1 の場合、extgcd(a, M, x, y) として x が a の逆元。

// ax+by=gcd(a,b)
ll extgcd(ll a, ll b, ll &x, ll &y) {
   ll g = a; x = 1; y = 0;
   if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
   return g;
}

特に M が素数の場合、フェルマーの小定理より a**(M-2) mod M が a の逆元。

a**(M-1) ≡ 1 mod M → a * a**(M-2) ≡ 1 mod M なので。

参考

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Cong.html

http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/Fermat.html

http://www.prefield.com/algorithm/math/gcd.html