Spaghetti Source logo

法 n の下での逆元

説明

x a == 1 (mod n) を満たす x が存在するかどうか判定し,存在すれば求める.拡張互助法のアプリケーション.

計算量

O(log n)

ソースコード

Int invMod(Int a, Int m) {
  Int x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;
  else                         return 0; // unsolvable
}

Verified

前原 貴憲(maehara@prefield.com).

Last Modified: 2007.11.14 19:22:01.