法上の演算と積の保守

概要

法上の基本演算を先に確立し、そのうえで「積から旧因子を逆元で外す」操作に必要な可逆性と、法 m で剰余 0 となる因子では逆元が存在しない境界を独立した動的保守技能として学ぶ。

考え方

法を整数 m≥2m\geq2 とする。加減乗算では途中で剰余を取っても最後の剰余は変わらないが、整数の割り算では同じ扱いができない。法上で因子を取り除くには、その因子に掛けると1になる数、すなわち逆元を使う。例えば法7では 3⋅5≡1(mod7)3\cdot5\equiv1\pmod7 なので、積 2⋅3≡62\cdot3\equiv6 から3を外す操作は 6⋅5≡26\cdot5\equiv2 となる。

一方、法7で因子7を掛けると積は0になり、逆元で取り除くこともできない。後でその因子を外して積を復元したいなら、剰余0の因子の個数と、それ以外の因子の積を別々に保持する必要がある。

まず四則演算・高速累乗・逆元で、整数除算との違いと逆元を使える条件を確認する。続く法上の動的積では、複数の剰余0因子が消えたときにも積を復元できる更新を追う。

成立条件と計算量

法 mm が素数なら、非零剰余 aa の逆元は am−2 mod ma^{m-2}\bmod m を二分累乗して O(log⁡m)O(\log m) 回の算術演算で求められる。逆元が既知なら、一因子の削除・差し替えは O(1)O(1) 回の算術演算で済む。

合成数法では、非零であるだけでは逆元の存在を保証できない。取り得る非零因子がすべて可逆なら同じ更新を使えるが、非可逆な非零因子も扱うには、法の素因数ごとの指数と可逆部分へ分けるなど別の表現が必要になる。積が0であることと、どの因子が非可逆かは同じ情報ではない。

下位単元

問題一覧

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

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

関連問題

前提・学習成果・出典

導入対象の目安: 緑色(800–1199)。法上の四則演算と逆元の存在条件を確認し、積の更新へ進む入口。

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

概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

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

前提と範囲

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

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

このUnitでは扱わないもの

  • 一次合同・CRT、剰余列の周期、乗法的位数、および法をまたいだ合同条件の統合。

根拠