noshi91のメモ

データ構造のある風景

mod 逆元と拡張ユークリッド互除法

概要

本稿では整数の  \bmod M での逆元について取り扱います。
文中の合同式 \bmod M です。

  • 拡張ユークリッド互除法で逆元を求める
  • 互除法の手順を高速化できるかもしれないという提案
  •  1 から  N の逆元を  \Theta ( N ) で計算する
  •  N 個の数について全ての逆元を  \Theta ( N + \log M ) で計算する (おまけ)


拡張ユークリッド互除法で逆元を求める

 a の逆元を計算します。 以下の形の合同式を考えます。
 s \equiv ta
もし  s = 1 なら  t が求める逆元となります。

ここで、明らかな合同式として以下の  2 つがあります。
 M \equiv 0a
 a \equiv 1a
この  2 式を足し引きすると、新たな合同式が得られます。 例えば
 M - 2a \equiv (0 - 2)a
などです。 よって、 M aユークリッドの互除法を行い  t も同時に管理すると、 s = 1 となり逆元が求まります。

 : M = 7 , a = 5
 7 \equiv 0 * 5 \qquad \cdots ①
 5 \equiv 1 * 5 \qquad \cdots ②
 2 \equiv 6 * 5 \qquad ( ① - ② ) \qquad \cdots ③
 1 \equiv 3 * 5 \qquad (② - 2 * ③)
 \therefore 5 ^{-1} \equiv 3


互除法のショートカット

 s \equiv ta について、 s の逆元  s ^ {-1} が既に分かっていたとします。 すると両辺に  s ^ {-1} を掛けることで  1 \equiv ( s ^ {-1} t ) a となり、 a の逆元が得られます。
普通は  s = 1 となったときに互除法を停止しますが、例えば  1 から  N までの逆元を前計算していた場合、 s \le N となった時点で終了できることになります。  s はおおまかに指数的に減少するため、 N = \lceil \sqrt M \rceil まで計算しておけば逆元が  2 倍速程度になることが見込めるかもしれません。


 1 から  N までの逆元を  \Theta ( N ) で計算する

互除法を  1 手順だけ進めたときを考えてみます。
 M \equiv 0a
 a \equiv 1a
 \displaystyle M \bmod a \equiv - \lfloor \frac M a \rfloor a
前述したように、もし  ( M \bmod a )  ^ {-1} が計算済であれば  \Theta ( 1 ) で逆元が得られます。 ここで  M \bmod a \lt a であるため、 a の昇順に逆元を計算することでこれは達成できます。 よって全体で  \Theta ( N ) の時間計算量となります。


 N 個の数について全ての逆元を  \Theta ( N + \log M ) で計算する

数列  a _ 0 \ldots a _ { N - 1 } のそれぞれについて逆元を計算します。
先頭からの累積積  p _ i := \prod _ { k \lt i } { a _ k } と末尾からの累積積  s _ i := \prod _ {i \lt k} {a _ k} \Theta ( N ) で計算します。
次に、全要素の逆元の積  c := \prod {a _ i ^ {-1}} p _ N ^ {-1} によって  \Theta ( \log M ) で計算します。
すると、 a _ i ^ {-1} = c p _ i s _ i によって  \Theta ( 1 ) でそれぞれの逆元を計算可能です。