Gaussian整数・二平方和
概要
Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。
考え方
normと有理素数の三分類
Gaussian整数はZ[i]={a+bi | a,bは整数}で、i²=−1とする。積は (a+bi)(c+di)=(ac−bd)+(ad+bc)i、共役はa−bi、normは Nm(a+bi)=(a+bi)(a−bi)=a²+b² である。normは乗法的で、norm 1の単元(可逆な元)は±1,±iの四つだけである。非零のGaussian整数で割った複素数の実部・虚部を最近接整数へ丸めれば、余りのnormは除数のnormの半分以下になる。このEuclid除法によりgcdを計算でき、素因数分解も単元倍を除いて一意になる。一意分解と素数の分裂の根拠はBen Lynnの数論ノートも参照できる。
正整数Nの有理整数としての素因数分解を考える。有理素数のGaussian整数での振る舞いは次の三つに分かれる。
- 2は
2=−i(1+i)²と分岐する。1−i=−i(1+i)なので共役も単元倍で同じ素因子であり、Nm(1+i)=2。 - p≡1 mod 4は
p=π_p conjugate(π_p)と分裂する。π_p=x+yi、Nm(π_p)=pで、共役二因子は単元倍では一致しない。 - q≡3 mod 4はZ[i]でも素数のまま残り、Nm(q)=q²。実際、norm qの整数対があれば平方のmod 4の値0,1からq≡3とはなれない。qが非自明に分解できれば両因子のnormがqとなるため、分解もできない。
p≡1 mod 4の分解は、0≤x≤⌊√p⌋を走査し、p−x²が整数の平方y²かを調べれば構成できる。こうして見つけたπ_pを各pについて一つ固定する。大きなpでは、非零のzをmod pから一様に選び t=z^((p−1)/4) mod p がt²≡−1を満たすまで試し、Z[i]でgcd(p,t+i)を求める方法も使える。非平方のzなら条件を満たすので平均試行回数は2。gcdはpを割り、pそのものではなく、iを−tへ写すmod pの写像により単元でもないのでnorm pとなる。Euclid除法の商を丸めて計算し、その実部・虚部が必要なx,yとなる。除算の実部・虚部は共役を掛けて整数の分子とnormの分母で表し、丸めも整数演算で行う。
共役への指数配分で全ての解を構成する
N=2^e2 ∏_{p≡1 mod 4}p^ep ∏_{q≡3 mod 4}q^eq と書く。a²+b²=Nは、g=a+biとして g conjugate(g)=N を解くことと同じである。
qは共役で変わらないため、gでのqの指数がhなら積での指数は2hとなる。よってeqが奇数なら解はない。全て偶数なら、全解は次の形になる。
g=u (1+i)^e2 ∏_{q≡3 mod 4}q^(eq/2) ∏_{p≡1 mod 4}π_p^kp conjugate(π_p)^(ep−kp)
ここでu∈{1,−1,i,−i}、各kpは0,…,epから独立に選ぶ。2の因子には自由な配分がなく、normの指数を合わせるため(1+i)をちょうどe2個取る。pの共役二因子は、gでkp個とep−kp個を持てば、共役との積でどちらもep個になる。この式で構成したgのnormはNであり、逆に一意分解から他の形のgはない。
例えばN=25ではπ_5=2+iを固定し、kp=0,1,2から3−4i、5、3+4iを得る。四つの単元倍を取れば、軸上の(±5,0),(0,±5)と、(±3,±4),(±4,±3)の計12対を重複なく列挙できる。
符号・座標順を区別する計数
N>0なら、異なる指数配分は単元倍を除いて異なるgとなり、一つの非零gの四つの単元倍も互いに異なる。したがって、符号と座標順を区別する整数対(a,b)の個数は、qの奇数指数があれば0、なければ r2(N)=4∏_{p≡1 mod 4}(ep+1) である。計数だけならπ_pの座標を求める必要はない。
符号・座標交換を同一視する場合はこの個数を一律に8で割らない。軸上a=0またはb=0、対角線|a|=|b|では軌道が4対、それ以外では8対になる。列挙後に(|a|,|b|)を昇順へ正規化して集合へ入れるなど、要求された同一視に合わせる。N=0は(0,0)の1対のみで、四単元倍を別解として数えない。N<0は解がない。
成立条件と計算量
素因数分解に要する費用を別に数える。分解済みなら存在判定・計数は異なる素因数の数に比例する回数の整数演算で済む。構成に単純な平方走査を使う場合はO(Σ_{p≡1 mod 4}√p)回の平方判定、mod pの平方根とGaussian gcdを使う場合は各pで期待O(log p)回程度の乗算・除法が必要になる。いずれも任意精度整数の一演算を定数時間とする評価であり、実際には桁数の費用を含める。
固定因子(1+i)^e2とq^(eq/2)は高速累乗で作る。各pのπ_pとその共役の0,…,ep乗を順に前計算し、全kpの積を作って現在の候補に掛けて展開する。素因数の種類数をh、R=∏(ep+1)とすれば、固定因子にO(Σ_r log(e_r+1))、共役積の前計算にO(Σ_p ep)、展開にO(hR)回以内の整数・Gaussian乗算、最後に4R対の出力が必要。rは全素因数、pは1 mod 4の素因数を動く。R自体が大きい場合は計数式を使い、列挙量を無視して高速とは主張しない。指数が圧縮入力なら前計算量Σ_p epにも注意する。ABC444 G公式解説の合同条件付き計数へ進む際も、まずこの指数配分と、何を別解として数えるかを固定する。
問題一覧
- ABC444 G「Kyoen」 公式問題組合せ: 関数グラフのcycle・tree分解
技能・出典
主題: Gaussian整数・二平方和(Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。)。既習技能: 関数グラフのcycle・tree分解(後続が一意なグラフをcycleと流入木へ分け、各頂点が属する構造を特定できる。)。主タグ: Gaussian整数・二平方和 / 補助タグ: 関数グラフのcycle・tree分解
各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。
前提・学習成果・出典
習得対象の目安: 赤色(2800以上)。Gaussian整数の素因数分解と共役を使い、二平方和の構成・計数を行う。
対象色の読み方は本書の読み方を参照してください。
概念上の親: 数論。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。
Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-gaussian-integers-two-squares
Gaussian整数・二平方和
習得する技能
- Z[i]での素因数分解と共役を用い、整数の二平方和表現をprime exponentごとに構成・数え上げる。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
前提と範囲
共通前提: prereq-abc-advanced-v1 (1.0.0)。
直接の前提単元: 素因数分解と約数構造。
このUnitを直接前提とする単元: なし。
素因数・約数分解で得た考え方と実装を再利用し、Gaussian整数・二平方和の発動条件・正当化・境界を重複なく学ぶ。
このUnitでは扱わないもの
- Gaussian整数・二平方和の発動条件・不変量を使わず、実装部品だけを偶然共有する解法。