概要
本稿では整数の での逆元について取り扱います。
文中の合同式は です。
- 拡張ユークリッド互除法で逆元を求める
- 互除法の手順を高速化できるかもしれないという提案
- から の逆元を で計算する
- 個の数について全ての逆元を で計算する (おまけ)
拡張ユークリッド互除法で逆元を求める
の逆元を計算します。
以下の形の合同式を考えます。
もし なら が求める逆元となります。
ここで、明らかな合同式として以下の つがあります。
この 式を足し引きすると、新たな合同式が得られます。
例えば
などです。
よって、 と でユークリッドの互除法を行い も同時に管理すると、 となり逆元が求まります。
例
互除法のショートカット
について、 の逆元 が既に分かっていたとします。
すると両辺に を掛けることで となり、 の逆元が得られます。
普通は となったときに互除法を停止しますが、例えば から までの逆元を前計算していた場合、 となった時点で終了できることになります。
はおおまかに指数的に減少するため、 まで計算しておけば逆元が 倍速程度になることが見込めるかもしれません。
から までの逆元を で計算する
互除法を 手順だけ進めたときを考えてみます。
前述したように、もし が計算済であれば で逆元が得られます。
ここで であるため、 の昇順に逆元を計算することでこれは達成できます。
よって全体で の時間計算量となります。
個の数について全ての逆元を で計算する
数列 のそれぞれについて逆元を計算します。
先頭からの累積積 と末尾からの累積積 を で計算します。
次に、全要素の逆元の積 を によって で計算します。
すると、 によって でそれぞれの逆元を計算可能です。