法上の四則演算・高速累乗・逆元

概要

剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算・確率を計算する。

考え方

以下では法を整数 m≥2m\geq2 とする。加減乗算は各入力を剰余に置き換えて計算できるが、整数除算ではその順序を交換できない。例えば8を2で割ってから法7で剰余を取ると4になる。一方、先に8を剰余1へ置き換え、整数除算で小数部分を切り捨てると、結果は0になってしまう。

(8/2) mod 7=4,⌊8 mod 72⌋=0.(8/2)\bmod7=4,\qquad \left\lfloor\frac{8\bmod7}{2}\right\rfloor=0.

法上で「2で割る」とは、2を掛けると元の値に戻る剰余を求めることである。2⋅4≡1(mod7)2\cdot4\equiv1\pmod7 なので、2の逆元は4である。従って剰余1に対する除算は 1⋅2−1≡1⋅4≡4(mod7)1\cdot2^{-1}\equiv1\cdot4\equiv4\pmod7 と計算でき、元の整数商の剰余と一致する。割り切れる整数の商を求めたい場合も、分母が可逆ならこの方法でよい。切り捨てを伴う一般の整数除算まで逆元の乗算に置き換えられるわけではない。

整数 aa の逆元が存在する条件は gcd⁡(a,m)=1\gcd(a,m)=1 である。拡張ユークリッドの互除法で整数 s,ts,t を求め、as+mt=1as+mt=1 と表せれば、s mod ms\bmod m が逆元になる。逆に逆元があれば同じ形の整数の等式が得られるので、最大公約数は1でなければならない。例えば法6で非零の2は可逆ではない。2x mod 62x\bmod6 は0、2、4のいずれかで、1にはならないためである。

法が素数 pp なら、a≢0(modp)a\not\equiv0\pmod p に対してフェルマーの小定理より ap−1≡1(modp)a^{p-1}\equiv1\pmod p となるので、ap−2a^{p-2} を逆元にできる。この累乗を高速に計算するのが二分累乗である。

整数 aa と非負整数 KK に対して aK mod ma^K\bmod m を求めるには、res=1\mathrm{res}=1、power=a mod m\mathrm{power}=a\bmod m、k=Kk=K で始める。次の操作を k=0k=0 になるまで繰り返す。

  1. kk が奇数なら、res←res⋅power mod m\mathrm{res}\leftarrow\mathrm{res}\cdot\mathrm{power}\bmod m とする。
  2. power←power2 mod m\mathrm{power}\leftarrow\mathrm{power}^2\bmod m とする。
  3. k←⌊k/2⌋k\leftarrow\lfloor k/2\rfloor とする。

各反復の前後で res⋅powerk≡aK(modm)\mathrm{res}\cdot\mathrm{power}^k\equiv a^K\pmod m が保たれる。奇数なら余った一因子を res\mathrm{res} へ移し、残りの偶数個の因子を二つずつまとめるのが二乗と指数の半減である。終了時には res\mathrm{res} が答えとなり、K=0K=0 でも初期値1をそのまま返す。

整数 A,BA,B で表した確率 A/BA/B も、分母 BB の剰余が可逆であることを確認して A⋅B−1 mod mA\cdot B^{-1}\bmod m とする。整数として B≠0B\ne0 でも、BB が素数法 pp の倍数なら割れない。ABC228 Eでは累乗の底が法の倍数かを先に分岐し、ABC411 Eでは可逆な分母を使って期待値を表す。いずれも、法上の式変形を行う前に適用条件を確かめることが重要になる。

負の入力は、例えば ((a % m) + m) % m で 0≤r<m0\leq r<m の剰余 rr へ正規化する。法1では全値の剰余が0になるため、上の逆元を使う手順と分けて扱う。

成立条件と計算量

二分累乗は指数を毎回半分にするため O(log⁡(K+1))O(\log(K+1)) 回、正規化した剰余の逆元を求める拡張ユークリッドの互除法は O(log⁡m)O(\log m) 回の算術演算を行う。素数法の逆元を累乗で作る場合も O(log⁡m)O(\log m) 回となる。いずれも反復で実装すれば補助空間は O(1)O(1) である。

これらは各算術演算を定数時間とみなした評価である。乗算後に剰余を取っても、乗算そのもののオーバーフローは防げないので、中間積を保持できる整数型や乗算方法を選ぶ。合成数法へ am−2a^{m-2} による逆元計算を流用しない。

問題一覧

この単元に直接配置する問題はありません。下位単元または関連問題を参照してください。

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 緑色(800–1199)。二分累乗と逆元を実装し、整数の割り算と法上の除算を区別する。

対象色の読み方は本書の読み方を参照してください。

概念上の親: 法上の演算と積の保守。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-modular-arithmetic

法上の四則演算・高速累乗・逆元

習得する技能

  • 剰余を正規化して加減乗算し、二分累乗と可逆性を確認した逆元により法上の除算・確率を計算できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: Baby-Step Giant-Step・可逆作用の反復到達探索、可逆な非零剰余と剰余 0 因子を含む法上の動的積、拡大有限体の表現と四則演算を構成する、標数pのFrobenius恒等式による反復高速化、一般グラフの最小重み完全matching、一次合同・CRTで解の類を統合する、剰余周期と指数法則を利用する、乗法的位数から最小周期を求める。

剰余を正規化して加減乗算し、二分累乗と逆元の存在条件を使って法上の除算や確率を計算する。

このUnitでは扱わないもの

  • 法 m で剰余 0 となる因子数と可逆な非零剰余因子の積を分けて因子差し替えを処理する動的積、複数の合同条件を統合する一次合同・CRT、および剰余列の最小周期を求める問題。

根拠