有限体パッケージ

体とは,四則演算の規則に従った代数構造のことである.特に,体は加算と乗算の二項演算を持つ.どちらの二項演算も可換性および結合性がある.体には,加法単位元0と乗法単位元1の2つの特殊な元がある.このパッケージでは,体の元に対する演算が適切に定義されるように, PlusTimesPowerに規則を追加する.また,有限体を扱うため,また有限体の元を設定するための低レベルのユーティリティも提供している.

どの有限体にも体の標数と呼ばれる固定された素数 がある.体の元1の 個の和が体の元0となる.標数 の有限体には,大まかに拡大次数と呼ばれる任意の正の整数 について 個の元がある.このパッケージでは,体の元を一変数多項式として表す.多項式の次数は最大 次で,係数は を法とする整数である.

有限体の元の内部形式は,GF[p,ilist][elist]である.ここでGFとはガロア体, とは体の素数標数,ilist とは体における乗法を定義する既約多項式の係数リスト,elist は特定の元を表す多項式の係数リストのことである.この形式は少し煩雑なので,このパッケージでは有限体の元を入力するためのショートカットを提供している.

GF[p][{k}]p を法とする整数体の中の整数 k
GF[p,1][{k}]p を法とする整数体の中の整数 k を表す別の方法
GF[p,{0,1}][{k}]p を法とする整数体の中の整数 k の完全形
GF[p,d]p を法とする整数)と同形の素体の拡大体で,拡大次数が d である体.自動的に既約多項式が選ばれる
GF[p,ilist][elist]有限体の元の完全形.ここで ilist は既約多項式の係数を表す長さ の整数のリストであり,elist はその元の多項式表現の係数を与える長さ d の整数のリストである

有限体の元の入力方法

パッケージをロードする.
In[1]:=
Click for copyable input
7を法として4と5を足す.デフォルトの出力形式は,下付き文字となる.
In[2]:=
Click for copyable input
Out[2]=
以下は式のFullFormである.自動的に既約多項式が選ばれることに注意.
In[3]:=
Click for copyable input
Out[3]//FullForm=
個の元を持つ体での乗算である.
In[4]:=
Click for copyable input
Out[4]=
体のオブジェクトは自動的に標準形に簡約される.
In[5]:=
Click for copyable input
Out[5]=
Wolfram言語は多項式を定数項から並べていくので,有限体の元についても同様に表現される.以下の例では,入力における左側の0は定数項を与えるのに必要だが,右側の0は必要なものではない.
In[6]:=
Click for copyable input
Out[6]=
異なる有限体の元を加えることは意味をなさないので,以下の式は評価されない.
In[7]:=
Click for copyable input
Out[7]=
整数は有限体にインポートされる.
In[8]:=
Click for copyable input
Out[8]=

ゼロは特殊である.このパッケージでは,どの体にあるかに関わらずゼロはゼロと想定している.この結果,体の元ゼロは自動的に整数0に簡約される.Wolfram言語の関数の多くはこの想定のもとでよりよいパフォーマンスが期待できる.この想定は,厳密に言えば正しくないが,無意味な入力がされない限り無意味な出力を生成しない.

体の元ゼロは演算後に整数のに簡約される.
In[9]:=
Click for copyable input
Out[9]=
異なる体からの元ゼロの合計もに簡約される.
In[10]:=
Click for copyable input
Out[10]=
SetFieldFormat[f,FormatType->Subscripted]f の出力がSubscriptedとなるよう設定する(デフォルト)
SetFieldFormat[f,FormatType->FullForm]f の出力がFullFormとなるよう設定する
SetFieldFormat[f,FormatType->FunctionOfCoefficients[g]]体の元の多項式表現の係数により与えられる引数を取る関数 g を使って,体 f が元を入力・出力するよう設定する
SetFieldFormat[f,FormatType->FunctionOfCode[g]]体の元を指定する整数コードにより与えられる引数を取る関数 g を使って,体 f が元を入力・出力するよう設定する

体の元のフォーマット

有限体の元をFullFormで常に入力・出力することは可能であるが,このパッケージではショートカットもいくつか提供している.素体の元はGF[p][{k}]あるいはGF[p,1][{k}]と書くことができ,そのどちらともGF[p,{0,1}][{k}]であると解釈される.一般に, が素数, が正の整数ならば,GF[s]GF[p,d]であると解釈される.式GF[3, 4]は3を法とした拡大次数が4の整数,つまり81の元を持つ体を表している.このパッケージでは,この形式が使われると,ilist によって与えられる係数を持つ既約多項式,およびGF[p,ilist][{0,1}]が体の原始元という特性を持つ既約多項式が自動的に選ばれる.しかし,GF[3,{1,1,1,1,2,1}]のように明示的に示すことにより,自分で既約多項式を与えることもできる.

有限体の元のデフォルトであるOutputFormは体の標数が下付き文字となる整数のリストである.このリストの長さは,素体上の拡大体の次数である.任意の体を1つだけ扱っているときは,指定された元がどの体に含まれているかを判別するのにデフォルトで十分である.

異なる既約多項式を使うと同じ大きさの体を複数作ることができるので,これらの体の元が判別できると便利である.また,有限体の元を入力するより簡単な方法があるのも役に立つ.関数SetFieldFormatは元の入力および出力形式を構築する.すでに説明した方法で元を入力することは常に可能であり,明示的に出力をFullFormにすることもできる.

GF[2,3]のような体の頭部がシンボルに割り当てられている可能性があることに注意.f8=GF[2,3]という割当てにより,を使って特定の元を参照することができる.

9個の元を持つ体に関数形式を与える.
In[11]:=
Click for copyable input
上記の体の元による演算.
In[12]:=
Click for copyable input
Out[12]=
各元を多項式の係数の列としてではなく,0から8の範囲の整数として表す.
In[13]:=
Click for copyable input
以下では,演算結果がコード化されている.
In[14]:=
Click for copyable input
Out[14]=
この体のデフォルト形式を復元する.
In[15]:=
Click for copyable input
Characteristic[f]f の標数を与える
ExtensionDegree[f]基礎体上の体 f の拡大次数を与える
FieldSize[f]f の元の数を与える
FieldIrreducible[f,s]f の乗算を定義する既約多項式をシンボル s で与える
IrreduciblePolynomial[s,p,d]素数 p を法とする整数上の d 次の既約多項式をシンボル s で与える

体のパラメータ関数

CharacteristicExtensionDegreeFieldSizeFieldIrreducibleIrreduciblePolynomialの5つの関数は,有限体について重要なパラメータを与える.

Characteristicは体の素数の標数を与える.
In[16]:=
Click for copyable input
Out[16]=
拡大体とは,基礎体のベクトル空間である.ExtensionDegreeはこのベクトル空間の次元を与える.
In[17]:=
Click for copyable input
Out[17]=
FieldSizeは体における元の数を与える.
In[18]:=
Click for copyable input
Out[18]=
恒等式である.
In[19]:=
Click for copyable input
Out[19]=
体に関連した既約多項式を与える.
In[20]:=
Click for copyable input
Out[20]=
Successor[elem]元を通常の順序に並べたときの次の元を与える(この関数は繰り返さないので,最大の元には次の元がない)
ReduceElement[elem]元を既約された形式で与える
ToElementCode[elem]体の元をコード化する,体の大きさより小さい非負の整数を与える
FromElementCode[f,code]体の大きさよりも小さい非負の整数 code に対応する f の元を与える
PolynomialToElement[f,poly]整数値の係数を持つ一変数多項式 poly に対応する f の元を与える
ElementToPolynomial[elem,s]体の元 elem に対応するシンボル s の多項式を与える

元の操作の関数

SuccessorReduceElementToElementCodeFromElementCodePolynomialToElementElementToPolynomialの6つの関数は,有限体の元を扱うためのものである.

要素を多項式として表す.
In[21]:=
Click for copyable input
Out[21]=
PowerListQ[f]体の原始元のベキ乗を表すリストが体の演算に使われる場合はTrue,使われない場合はFalseを返す
FieldExp[f,n]整数 n について,体 f に関連する離散指数関数の値を与える
FieldInd[elem]elem について,体に関連する離散対数関数の値を与える
PowerList[f]体の原始元を整数ベキ乗0, 1, 2, , FieldSize[f]-1に上げることで生成された体 f の非零の元のデータ部分のリストを与える
PowerListToField[list]元のデータ部分の指定されたリストに対応する体を与える.ここの元とは,原始元の連続したベキ乗によって生成されたものである

高速の乗算・除算をサポートする関数

有限体は,素数乗の数の元を持たなければならない.有限体に 個の元があり, が素数とすると,これは を法とする整数と同形である.この場合,このパッケージは整数に対して通常通り加算,減算,乗算,正のベキ乗を行い,Modを使って結果を簡約する.負のベキ乗にはPowerModを使用する.

体に 個の元()がある場合は,次数が より小さく, を法とする整数の係数を持つある変数についての1組の多項式と同形である.加算は,係数が を法として簡約されることを除いて,多項式の加算と同じである.乗算では,積は を法とする整数上の(因数分解不可能な)既約多項式を法として簡約される.

乗法の逆数を取ることは,既約多項式で を法とする拡張最大公約数の係数を求めることと同じである.つまり,体の元 elem と体の既約多項式 irred があるとしたときに,PolynomialGCD[elem,irred,Modulus->p]PolynomialMod[a elem + b irred,p]と同じになるような多項式 を見付けるのである.PolynomialGCDの結果が一致していれば,elem の逆数である.

任意の有限体の乗法群は巡回的であるという事実に基づくと,乗算を行ったり逆数を計算したりするより早い方法がある.群の生成元とその生成元の正のベキ乗のリストが順にあるなら,乗算と除算はリスト内の要素の指数の加算・減算に簡単化することができる.

このパッケージは,原始元のベキ乗を表すリストから体のオブジェクトを生成(PowerListToField)すること,あるいは,体のオブジェクトから原始元のベキ乗を表すリストを生成(PowerList)することを可能にすることにより,上記の計算方法をサポートしている.PowerListQTrueと設定すると,離散指数関数FieldExpと離散対数関数FieldIndを定義することにより,体の演算に原始元のベキ乗のリストが使われるようになる.FieldInd関数は体の指標関数と呼ばれることがよくある.ベキ乗のリストは,どの原始元を選ぶか,また,体の表現にどの既約多項式を使うかに依存している.FieldInd[elem]FieldSize[f]-1と互いに素である体の元はすべて,その体の原始元でもある.

原始元のベキ乗のリストを使った体の演算には2つの欠点がある.リストの入力もしくは計算に時間がかかるということと,リストがかなりのメモリを使用する可能性があるという点である.一般に,少数の演算しか行っていない場合や大きい体を扱っている場合は,リストを作成しない方がよい.PowerListQFalseと設定すると,特定の体でこの演算方法が使えなくなるが,FieldExpFieldInd計算された値を破壊することはない.

3が7を法とする整数の原始元であることを示している.もう1つの原始元は5である.GF[7,1]は素体なので,原始元のベキ乗のリストを使った乗算は役に立たない.
In[22]:=
Click for copyable input
Out[22]=
原始元のベキ乗のリストを使ってGF[7,1]の演算を行うことは効率は悪いが,可能ではある.
In[23]:=
Click for copyable input
PowerListの位置はFieldIndによって与えられる指標よりも1つ大きい.
In[24]:=
Click for copyable input
Out[24]=
FieldExpFieldIndは逆である.
In[25]:=
Click for copyable input
Out[25]=
体の標数と体の指数の定義は通常の定義の一部ではないが,アプリケーションによっては役に立つかもしれない.
In[26]:=
Click for copyable input
Out[26]=

書籍の中には,PowerListによって与えられるリストと同等の表を含んでいるものもある.関数PowerListToField,そのようなリストを使って体を定義することを可能にする.PowerListToFieldの引数は 組の整数の のリストである.最初の 組は体の個の元を表す多項式の係数を与えるものとされている.これは係数の定数項が最初にリストされるか最後にリストするかを決定するために使われる.2番目の 組は体の原始元を表すものと想定されている.この後の 組は2番目の元に続くベキ乗を表すものと想定されている.PowerListToFieldは初歩的なエラーチェックを行い,入力リストが妥当であることを検証する.妥当であれば,PowerListToFieldは標数や既約多項式など,体のパラメータを計算する.

以下は9次の体である.
In[27]:=
Click for copyable input
Out[27]=
PowerListToFieldを使って定義された体は演算可能である.
In[28]:=
Click for copyable input
Out[28]=
体のパラメータは自動的に計算される.
In[29]:=
Click for copyable input
Out[29]=
FieldExpはもとのリストに対応する元のリストを作成するために使用することができる.
In[30]:=
Click for copyable input
Out[30]=
これは元のデータ部分からなるもとのリストを与える.
In[31]:=
Click for copyable input
Out[31]=

他のWolfram言語関数との互換性

ほとんどのWolfram言語関数は任意の体で動作するようには設計されておらず,実際そのように設計することは不可能である.例えば,有限体のオブジェクトを含む式を積分しても無意味である.せいぜいそのような関数は,そのような式が与えられても何もしないであろう.

通常,このような関数は体のオブジェクトを未知のシンボルとして扱うものと想定できる.有限体のオブジェクトを持つ式に対して関数を使う前に,まずテストしてみるのが賢明である.合理的に動作すると思われる関数のタイプには,線形代数関数と多項式関数がある.

GF[9]の形式を設定する.
In[32]:=
Click for copyable input
分数乗は計算できない.
In[33]:=
Click for copyable input
Out[33]=
Factorは有理数を想定した関数であり,ここでは使えない.
In[34]:=
Click for copyable input
Out[34]=
PolynomialGCDも使えない.代りに,このパッケージで定義されているPolynomialExtendedGCDを使う.
In[35]:=
Click for copyable input
Out[35]=
GF[3,4]の形式を設定する.
In[36]:=
Click for copyable input
PolynomialQuotientPolynomialRemainderは体上の多項式を取る.
In[37]:=
Click for copyable input
Out[37]=
PolynomialModは整数上の多項式には使えるが,体上の多項式には使えない.Wolfram言語はGFオブジェクトを数値として扱わないので,体上の多項式は自動的には昇ベキの順に並べられない.
In[38]:=
Click for copyable input
Out[38]=
Detは体の元の行列に使える.
In[39]:=
Click for copyable input
Out[39]=
RowReduceは1が体の中になければならないことを除いて,動作する.
In[40]:=
Click for copyable input
Out[40]=
InverseDotも体の元の行列に使える.
In[41]:=
Click for copyable input
Out[41]=