剰余周期と指数法則を利用する

概要

剰余周期・指数法則

有限剰余状態の周期またはFermat/Euler型指数簡約を示し、巨大な反復やtower exponentを短縮する。

考え方

反復列の剰余状態は有限なので、決定性遷移ではいつか同じ状態へ戻る。cycleに入る前のprefixと、cycle長を分ければ巨大回数を剰余へ移せる。

決定性遷移fでは、初期sから状態列state[t]とfirst[state]を持ち、未登録状態を時刻tで記録して進める。既出stateへ戻った時刻がt、その初出がμなら周期λ=t−μ。K<μではstate[K]、K≥μでは state[μ+(K−μ) mod λ] を返す。Kそのものを最初からλで割ると、前周期を含む場合に別状態へ写してしまう。

gcd(a,m)=1ならEulerの定理でa^φ(m)=1だから、非負指数EはE mod φ(m)へ簡約できる。素数pでは非零aに対しp−1を使う。towerの上段を別の法で評価するときも、この可逆性を段ごとに確認する。例えばa≡0 mod pではE=0なら1、E>0なら0であり、Eをp−1で割って0にしただけでは両者を区別できない。非可逆な場合は素数冪ごとの指数飽和条件や前周期を別に扱う。

成立条件と計算量

状態数Sなら直接cycle検出O(S)時間、訪問記録O(S)空間。Floyd法なら空間を減らせる。乗法だけの周期が群の位数で決まるのは可逆な元の場合で、非可逆な元には前周期があり得る。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 青色(1600–1999)。Fermat・Euler型の指数簡約で必要な互いに素条件と周期を確認する。

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

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

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

習得する技能

  • 剰余類上の周期または指数法則を示し、周期状態の前計算や巨大指数の簡約で値を求められる。

前提と範囲

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

直接の前提単元: 法上の四則演算・高速累乗・逆元。

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

剰余列や冪が有限状態で周期化することを示し、周期前計算や指数法則で巨大な反復を短縮する。

このUnitでは扱わないもの

  • 逆元・一次合同・CRTによる合同条件の統合、および巡回群の位数を使う計数。

根拠