巡回群を指数化して数える

概要

巡回群の指数化・位数別数え上げ

冪を繰り返して到達できる元を数えるときは、各元の値よりも、何乗で初めて1に戻るかに注目する。同じ巡回群では、この周期が等しい元は同じ集合へ到達する。そこで元を位数でまとめ、約数の関係で数える。

考え方

法7で元・位数・生成する部分群を区別する

素数 PP を法とする非零剰余 1,…,P−11,\ldots,P-1 は、乗法について巡回群をなす。これは、ある元 gg の冪で全非零元をちょうど一巡できるという意味である。この gg を群全体の生成元(法 PP の原始根)と呼ぶ。群に含まれる元の個数を群の位数といい、ここでは q=P−1q=P-1 である。

法7では g=3g=3 を使える。指数を0から5まで動かすと、次のようになる。元 xx の位数 ord⁡(x)\operatorname{ord}(x) は、xt≡1(mod7)x^t\equiv1\pmod7 となる最小の正整数 tt である。

指数 ee元 3e mod 73^e\bmod7位数
011
136
223
362
443
556

例えば2の正の冪は 2,4,1,2,…2,4,1,2,\ldots、4の正の冪は 4,2,1,4,…4,2,1,4,\ldots と巡る。両者は別の元だが、位数はともに3であり、生成する部分群は同じ {1,2,4}\{1,2,4\} である。元 xx の冪で得られる部分群を ⟨x⟩\langle x\rangle と書くと、⟨2⟩=⟨4⟩\langle2\rangle=\langle4\rangle となる。2と4はこの部分群の生成元であり、群全体の生成元ではない。

一方、⟨6⟩={1,6}\langle6\rangle=\{1,6\} は位数2の部分群である。{1,2,4}\{1,2,4\} と {1,6}\{1,6\} はどちらも他方を含まない。元の位数の大小だけでは、冪で到達できるかは決まらない。 単位元1は位数1で、どの非零元 xx からも正の冪 xord⁡(x)x^{\operatorname{ord}(x)} で到達できるが、1から到達できるのは1だけである。

位数ごとの元の個数を指数から導く

位数 qq の巡回群 G=⟨g⟩G=\langle g\rangle では、各元は x=gex=g^e、0≤e<q0\leq e<q と一意に書ける。乗法は指数の加算に、冪は指数の乗算に移る。ただし指数は qq を法として扱う。

xx の位数を求める条件は、

(ge)t=1⟺q∣et(g^e)^t=1\quad\Longleftrightarrow\quad q\mid et

である。h=gcd⁡(q,e)h=\gcd(q,e) とおくと、q/hq/h と e/he/h は互いに素なので、右辺は q/h∣tq/h\mid t と同値になる。最小の正整数 tt を取れば、

ord⁡(ge)=qgcd⁡(q,e)\operatorname{ord}(g^e)=\frac{q}{\gcd(q,e)}

を得る。法7の表も、指数 0,1,2,3,4,50,1,2,3,4,5 と6のgcdから位数 1,6,3,2,3,61,6,3,2,3,6 を計算したものである。e=0e=0 では gcd⁡(q,0)=q\gcd(q,0)=q なので、単位元の位数も1になる。

従って元の位数は qq の約数に限られる。約数 d∣qd\mid q に対し、位数が dd である条件は、

e=qdu,0≤u<d,gcd⁡(u,d)=1e=\frac{q}{d}u,\qquad 0\leq u<d,\qquad \gcd(u,d)=1

と書ける。d>1d>1 なら、このような uu の個数はオイラーのトーシェント関数 φ(d)\varphi(d)、すなわち 1,…,d1,\ldots,d のうち dd と互いに素な整数の個数である。d=1d=1 では e=0e=0 の1個だけで、φ(1)=1\varphi(1)=1 と一致する。

法7では、位数1の元が1個、位数2が1個、位数3が2個、位数6が2個となる。位数3の2と4は同じ部分群を生成するが、元を数えるときは2個、生成する部分群を数えるときは1個である。

冪での到達を部分群の包含へ移す

d∣qd\mid q に対し、gq/dg^{q/d} が生成する位数 dd の部分群を HdH_d とする。位数 dd の元は上で見た g(q/d)ug^{(q/d)u} の形を持つ。uu と dd が互いに素なら、その元の冪は gq/dg^{q/d} の冪を順番を変えてすべて巡る。つまり、位数 dd の元はどれも同じ HdH_d を生成する。

この部分群は、指数が q/dq/d の倍数である元の集合である。よって d,e∣qd,e\mid q に対して、

He⊆Hd⟺e∣dH_e\subseteq H_d\quad\Longleftrightarrow\quad e\mid d

となる。実際、e∣de\mid d なら gq/e=(gq/d)d/eg^{q/e}=(g^{q/d})^{d/e} なので包含が成り立つ。逆に包含があれば、HeH_e の生成元 gq/eg^{q/e} の指数も q/dq/d の倍数となり、e∣de\mid d が必要になる。巡回群の部分群も巡回群なので、位数 dd の部分群はこの HdH_d だけである。

yy が xx の冪であることは、⟨y⟩⊆⟨x⟩\langle y\rangle\subseteq\langle x\rangle と同値である。従って、ある正整数 nn に対して xn=yx^n=y となる条件は、

ord⁡(y)∣ord⁡(x)\operatorname{ord}(y)\mid\operatorname{ord}(x)

である。指数0で得られる1も、指数を ord⁡(x)\operatorname{ord}(x) に置き換えれば得られるため、正整数の冪という条件で困らない。法7で2から4へも4から2へも到達できるのは位数が等しいからであり、2と6の間でどちら向きにも到達できないのは、3と2が互いを割らないからである。

指数で直接見るなら、x=ga,y=gbx=g^a,y=g^b に対して xn=yx^n=y は an≡b(modq)an\equiv b\pmod q となる。この合同式が解を持つ条件は gcd⁡(a,q)∣b\gcd(a,q)\mid b であり、位数を使った条件と同じである。

全元を数えるか、入力の頻度を数えるか

ABC212 Gの解説へ進むときは、全非零元が候補であることを使う。位数 dd の始点は φ(d)\varphi(d) 個あり、各始点からは生成部分群の dd 個の元へ到達する。従って非零元の順序付き対の個数は、

∑d∣qφ(d)d\sum_{d\mid q}\varphi(d)d

である。法7なら 1×1+1×2+2×3+2×6=211\times1+1\times2+2\times3+2\times6=21 組となる。0を含む対は非零群から分ける。正の冪では0から到達するのは0だけで、非零元の冪が0になることもないので、(0,0)(0,0) の1組を足して22組となる。

ABC335 Gの解説へ進むときは、与えられた入力の添字を区別する必要がある。位数 dd の入力の個数を F(d)F(d) とすれば、求める順序付き対の個数は、

∑d∣qF(d)∑e∣dF(e)\sum_{d\mid q}F(d)\sum_{e\mid d}F(e)

となる。始点の位数 dd を固定し、到達先の位数 ee が dd を割る入力を数える式である。入力の重複を消したり、F(d)F(d) を全元についての個数 φ(d)\varphi(d) へ置き換えたりしてはいけない。

独自の小例として、法7で入力が (2,2,4,6,1)(2,2,4,6,1) なら、F(3)=3,F(2)=1,F(1)=1F(3)=3,F(2)=1,F(1)=1 である。位数3の始点3個からは、それぞれ位数3の3個と位数1の1個へ到達する。位数2の始点からは2個、位数1の始点からは1個へ到達するので、合計は 3×4+1×2+1×1=153\times4+1\times2+1\times1=15 組となる。2が重複した二つの位置は別々に数え、始点と終点が同じ添字の対も含める。順序付きなので、2の位置から1の位置への対は数えるが、逆向きの対は数えない。この問題の入力は非零元だけなので、0の寄与は加えない。

約数ごとの頻度和は約数格子のzeta・Möbius反転へつながる。復習では、冪で得られる集合を位数で分類し、数える対象に応じた個数を掛けるという二段階を思い出したい。

指数化で扱えるほかの条件

正整数 aa に対し、群内の未知元 x=gex=g^e について xa=1x^a=1 は ae≡0(modq)ae\equiv0\pmod q なので、解は gcd⁡(a,q)\gcd(a,q) 個ある。xa=gbx^a=g^b は gcd⁡(a,q)∣b\gcd(a,q)\mid b のとき同じ個数、それ以外は0個となる。これは始点 xx を固定して到達先を数える場合とは、未知数が異なる。

部分群 Hd,HeH_d,H_e の共通部分は Hgcd⁡(d,e)H_{\gcd(d,e)}、両者の元を使って生成する最小の部分群は Hlcm⁡(d,e)H_{\operatorname{lcm}(d,e)} になる。例えば法7では、H3∩H2={1}H_3\cap H_2=\{1\} であり、両者が生成する群は全非零元の群 H6H_6 である。一方、和集合 H3∪H2={1,2,4,6}H_3\cup H_2=\{1,2,4,6\} は4元で、H6H_6 とは異なる。和集合を数えるなら共通部分を引く。指数に移しても、任意の条件が独立になるわけではない。

成立条件と計算量

この分類を使うには、対象が同じ巡回群に属することが必要である。素数法の非零剰余では使えるが、合成数法の可逆元全体は巡回群とは限らず、同じ位数でも異なる部分群を生成することがある。0や非可逆元を含む範囲へ、位数の整除だけによる到達判定をそのまま広げない。

生成元による表示は証明の道具であり、実装で生成元や各元の指数(離散対数)を求める必要があるとは限らない。ABC212 Gでは q=P−1q=P-1 の約数ごとの個数だけを求められる。ABC335 Gでは、前提単元の位数を割り落とす手順で各入力の位数を直接求められる。必要なのが元の具体的な指数か、位数や頻度だけかを先に確認する。離散対数を実際に求める方針なら、その構築・計算費用も含める。

q=P−1q=P-1 の約数の個数を DD とする。試し割りによる素因数分解と約数列挙に O(q+D)O(\sqrt q+D) 時間を使い、約数の全対を調べて個数を集計するなら O(D2)O(D^2) 時間・O(D)O(D) 空間を使う。全非零元を数える場合は、位数 dd の元の個数を C(d)C(d) とし、C(d)=d−∑e∣d, e<dC(e)C(d)=d-\sum_{e\mid d,\ e<d}C(e) を小さい約数から計算すれば、HdH_d の元を位数別に分けられ、C(d)=φ(d)C(d)=\varphi(d) を得る。従ってこの方法の全体は O(q+D2)O(\sqrt q+D^2) 時間・O(D)O(D) 空間となる。

入力が NN 個ある場合は、その読み込みと位数の計算も必要になる。法上の乗算を O(1)O(1) と数えれば、位数削減は1入力あたり O((log⁡P)2)O((\log P)^2) 時間なので、約数の全対による集計まで含めて O(q+N(log⁡P)2+D2)O(\sqrt q+N(\log P)^2+D^2) 時間となる。入力を保存する実装では空間は O(N+D)O(N+D) である。約数和の集計を素因数の指数ごとの累積和に置き換える高速化はABC335 Gの解説で扱う。

問題一覧

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

前提・学習成果・出典

習得対象の目安: 黄色(2000–2399)。巡回群を指数へ写し、位数・gcd・約数の分類で重複なく数える。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-cyclic-group-exponent-counting

習得する技能

  • 巡回部分群を指数と約数格子で分類し、重複を補正して対象を数えられる。

前提と範囲

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

直接の前提単元: 乗法的位数から最小周期を求める。

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

乗法的位数とその約数分類を先に学び、巡回群の元を指数へ写して位数別に重複なく数える。個別問題で必要な約数Möbius反転はsupporting readinessとして接続する。

このUnitでは扱わないもの

  • 乗法的位数から最小周期だけを求める問題。

根拠