拡大有限体の表現と四則演算を構成する

概要

拡大有限体の表現と演算

素体上の多項式剰余または基底座標で有限体の元を表し、標準化された加減乗除を構成する。

考え方

まず二次拡大で四則演算を作る

奇素数p上で平方非剰余D(どのxにもx²≡D mod pとならない値)を選ぶ。形式的な元θにθ²=Dという関係を与え、全ての元を(a,b)、すなわちa+bθ(a,b∈F_p)で表す。二元の加減は座標ごと、乗算は展開後にθ²をDへ置き換えて

(a+bθ)(c+eθ)=(ac+Dbe)+(ae+bc)θ

とする。係数は毎回mod pへ正規化する。多項式X²−DがF_pに根を持たず既約であるため、p²個の座標が一意な元を表す。例えばp=3,D=2ならθ²=2で、θはF_3内には存在しない根になる。

非零元の逆元は共役を掛けて

(a+bθ)^{-1}=(a−bθ)/(a²−Db²)

で得る。分母が0でb≠0ならD=(a/b)²となって非剰余性に反する。b=0ならa²=0よりa=0なので元が零だったことになる。従って非零元の分母は必ずF_pの逆元を持ち、直接前提の法上の除算だけで構成できる。除算A/BはAにBの逆元を掛ける。pが奇数ならD候補を D^((p−1)/2)=−1 で判定できる。p=2ではこの二次式は使わず、例えばX²+X+1を用いる。

一般次数の係数配列と剰余化

次数dのmonicな既約多項式 h(X)=X^d+Σ_{j<d}h_j X^j を固定する。元Aは次数d未満の係数配列で表し、加減は成分ごとに行う。積の係数C_kを通常の積和で求め、k=2d−2からdへ降順に、係数C_kについて各j<dへ C_{k−d+j}−=C_k h_j を加え、C_k=0とする。これはX^d≡−Σ h_j X^jの置換であり、順に高次項を消して一意な次数d未満へ戻せる。

逆元では、非零Aとhに多項式Euclidを適用する。多項式除法は、余りRの最高係数を除数の最高係数で割り、その商係数の単項式倍をRから引く操作を次数が小さくなるまで繰り返す。Euclidの余り列はr0=h,r1=Aから r_{k+1}=r_{k−1}−q_k r_k。同時にr_k=s_k h+t_k Aを保ち、初期(s0,t0)=(1,0)、(s1,t1)=(0,1)、更新 (s_{k+1},t_{k+1})=(s_{k−1},t_{k−1})−q_k(s_k,t_k) とする。既約hと次数d未満の非零Aのgcdは非零定数gとなるので、最後のtをgで割ってhで剰余化すれば uA+vh=1、すなわちuが逆元になる。

別の構成として、体の非零元は位数p^d−1の乗法群を作るので、Aの逆元をA^(p^d−2)で求められる。既約性を証明してから使う性質であり、単に多項式で剰余を取っただけでは体になるとは限らない。

XORを加法に持つ二次拡大の塔

整数のbit列と加法XORを一致させたいなら、幅w=1,2,4,…,64のnimber表現を使える。Nim積はmex{(a'⊗b) xor (a⊗b') xor (a'⊗b'):a'<a,b'<b}で定義され、これらの幅の整数集合は体となる。高速な計算ではw=2hとしてθ=2^h、η=2^(h−1)、θ²=θ+ηを用いる。元aの下半分a_0、上半分a_1をa_0+a_1θと読み、係数積を下位体で行う。

c=a_1⊗b_1、d=a_0⊗b_0、e=(a_0 xor a_1)⊗(b_0 xor b_1)とすると、積の下半分はd xor (c⊗η)、上半分はd xor e。これを半分の幅へ再帰し、幅1では0/1の通常積で止める。ηの絶対traceは1であり、最初のη=1から、二次拡大の相対trace a+bθ→bを使って帰納できる。このためX²+X+ηは各段で既約となり、64bitの閉じた体を作る。

8bit以下の全256²組を、table参照を無効にした再帰で前計算する。64bitの積は64→32→16→8の三段、各段高々四つの下位積なので最大64回のtable参照で計算できる。非零元の逆元はa^(2^64−2)をこの積で累乗する。入力bit列を一般のGF(2^64)の多項式基底へ勝手に読み替えると乗法が変わるため、どの基底と関係を採用したかを固定する。XOR列のrolling hashへ使う場合は、この分配的な積をprefix更新とsubstring抽出の両方に用いる。

成立条件と計算量

係数配列の加減O(d)、素朴な積と剰余化O(d²)。素朴な拡張EuclidはO(d²)回の素体演算、累乗での逆元はO(d² log(p^d))回の素体演算である。素体逆元の計算費用と既約多項式を探す費用は別に数える。二次拡大は定数個の座標積と一回の素体逆元で割れる。既約でないhでは零因子が生じ、非零元にも逆元がない場合がある。

問題一覧

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

関連問題

前提・学習成果・出典

習得対象の目安: 橙色(2400–2799)。既約多項式や基底座標から有限体を構成し、四則演算の実装を正当化する。

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

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

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-finite-field-extension

習得する技能

  • 基底と既約関係を定めて拡大有限体の元を一意に表し、標準形を保つ加減乗除を実装できる。

前提と範囲

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

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

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

素体上の演算を土台に、既約関係で元を標準化し、加減乗除が閉じる拡大体として扱う。

このUnitでは扱わないもの

  • 素数法上の通常の四則演算だけで閉じる計算、および環上で逆元の存在を仮定できない演算。

根拠