拡張ユークリッド互除法まとめ - あめんばーどのバーチャル日記

基本的にはここで書いたModの割り算に関する言及の書き直しみたいなもんです。

【競プロ】個人的に優先度の高いライブラリ - あめんばーどのバーチャル日記

背景

Modの割り算にはその数の逆元を求める必要があり、それを求める方法としてフェルマーの小定理と、拡張ユークリッド互除法がある。

フェルマーの小定理

$P$ が素数なら $a^{P-1}≡1 (mod P)$ なので $b≡a^{P-2}(mod P)$ は逆元である。これは繰り返し二乗法を使えば $O(logP)$

拡張ユークリッド互除法

今回言及する内容なので後述

二つの速度的な違い

どちらも $O(logP)$ である。ただし例えば $P=1000000007$ の場合、フェルマーの小定理は常に30回。対して拡張ユークリッド互除法は1回～36回（平均は17.932回）
これはフェルマーの小定理は $log$ の底が $2$ に対し、ユークリッド互除法は最悪ケースがフィボナッチ数列の為 $\frac{1+\sqrt5}{2}$ なためである。

実際拡張ユークリッド互除法の最悪ケースのひとつ $920386740$ の逆元を $10^{7}$ 回分求めると、この通り拡張ユークリッド互除法のほうが遅い

拡張ユークリッドの互除法：4121ms
フェルマーの小定理：3129ms

逆に $2$ でやるとぶっちぎりで早い。

拡張ユークリッドの互除法：276ms
フェルマーの小定理：3185ms

期待値で考えるとやはりユークリッド互除法のほうが優れていそうである。とはいえ自分の中でも拡張ユークリッド互除法が曖昧だったのでいろいろ証明したりしたのでまとめた。って感じ

拡張ユークリッド互除法

コード

tuple<ll, ll, ll> extGcd(ll a, ll b) {
  if (b == 0) 
    return make_tuple(a, 1, 0);    // 行きがけのゴール地点
  auto [g, x, y] = extGcd(b, a % b);
  return make_tuple(g, y, x - y * (a / b));  // 帰りがけの動作
}

実装自体はこの4行で十分なのである。tupleはそれぞれGCDと下記を満たすx,yを返している。 $g=ax+by$