Conway多項式を使って有限体の表現を一意に定めよう

有限体を生成する既約多項式の選択

前回の記事では有限体の代数的閉包について調べた。その際、有限体の間の包含関係には、包含のさせ方が一意に定まらないという問題があることを述べた。その具体例として $\mathbb{F}_2[x]/(x^2+x+1) \to \mathbb{F}_2[x]/(y^4+y+1)$ という単射が一意に定まらないということを確かめた。

しかし、よく考えるとこれはあまり大した問題ではないのかもしれない。というのも、結局 $x \mapsto y^2+y,\ x+1 \mapsto y^2+y+1$ とするか $x \mapsto y^2+y+1,\ x+1 \mapsto y^2+y$ とするかだけの問題であり、行き先となる集合は変わらないからである。

ただし、ここでは1つ暗黙的に固定しているパラメータがあった。それは既約多項式の選択である。既約多項式として他のものを選べば具体的な集合の要素は変わってくる。もちろんどのような既約多項式で商体を作ろうが結果は全て同型ではあるのだが、具体的な表現の仕方が異なる。何か数学的に自然な既約多項式の選択方法はないものだろうか？

本稿ではこの問題を解決するアプローチの1つとして、Conway多項式を用いる方法を紹介する。ガッカリされないように先に述べておくと、既約多項式として数学的に自然なものをただ1つ選ぶようなうまいやり方はない。そんな中でも、多少なりともcanonical感のある選択をしようという話である。

注意

Conway多項式というのはどうやら複数の概念を表す言葉らしく、Wikipediaに曖昧さ回避のページがある[1]。本稿で言うところのConway多項式とは有限体に関するものであるため注意されたい。

Conway多項式

定義

Sageのドキュメントに書いてある定義が分かりやすいので引用する[2]。

Conway polynomial (Sageのドキュメント版）

The Conway polynomial $f_n$ of degree $n$ over $\mathbb{F}_p$ is defined by the following four conditions:

$f_n$ is irreducible.
In the quotient field $\mathbb{F}_p[x]/(f_n)$ , the element $x \bmod f_n$ generates the multiplicative group.
The minimal polynomial of $\left( x \bmod f_n \right)^{\frac{p^n-1}{p^m-1}}$ equals the Conway polynomial $f_m$ , for every divisor $m$ of $n$ .
$f_n$ is lexicographically least among all such polynomials, under a certain ordering.

The final condition is needed only in order to make the Conway polynomial unique.

これだけ見ると、最後の"lexicographically least"というところが良く分からない。これはWIkipediaの方の定義を見ると分かる[3]。

Conway polynomial (Wikipedia版）

The Conway polynomial $C_{p,n}$ is defined as the lexicographically minimal monic primitive polynomial of degree $n$ over $\mathbb{F}_p$ that is compatible with $C_{p,m}$ for all $m$ dividing $n$ . This is an inductive definition on $n$ : the base case is $C_{p,1}(x) = x - \alpha$ where $\alpha$ is the lexicographically minimal primitive element of $\mathbb{F}_p$ . The notion of lexicographical ordering used is the following:

The elements of $\mathbb{F}_p$ are ordered $0 < 1 < 2 < \ldots < p − 1$ .
A polynomial of degree $d$ in $\mathbb{F}_p[x]$ is written $a_d x^d - a_{d−1} x^{d-1} + \ldots + (-1)^d a_0$ and then expressed as the word $a_d a_{d - 1} \cdots a_0$ . Two polynomials of degree $d$ are ordered according to the lexicographical ordering of their corresponding words.

こちらの定義を見るとlexicographical orderingを具体的にどのように定めているかが分かる。逆に"compatible with $C_{p,m}$ for all $m$ dividing $n$ "というところが（私の引用の仕方の都合で）分かりづらいが、これは要するにSage版の定義に出てくる3つ目の条件を満たす必要があるということである。

また、 $m$ は $n$ を割り切る正の整数として定められているように見えるが、それで言うと $m$ として $n$ 自身も許されるはずである。しかし、それだとSage版定義の条件3にて再帰的に $f_n$ がConway多項式であることを確かめようとしているときに、 $f_n$ 自身がConway多項式であることが必要になるという意味不明な状況になる。そう考えると、恐らく暗黙的に $m < n$ が仮定されているのではないかと推測される。

Wikipedia版の定義ではConway多項式は原始多項式 (primitive polynomial) であると明記されているが、Sage版にはその記載がない。しかし、Sage版定義の条件2がそのまんま原始多項式であるための条件なので、同じことである。

辞書順で何かを選択するということ

前述のSage版定義の条件4では候補となる多項式を辞書順に並べて順序が最小となるものを選択している。これは非常に苦しい。というのも辞書順をどうやって決めるかというのは恣意性があり、数学的な構造から自然に決まるものではないからである。極端な話、順序を逆にしてもよいわけである。

辞書順で何かを選ぼうというのは、こういうcanonicalでない選択を迫られた時の苦肉の策として使うものなのだろう。

辞書順を決める際の各項の符号について

辞書順を定める際に各項の符号が正負交互になっているが、これはなぜだろうか？明確な理由は書かれていないので私の想像になるが、これはいわゆる「解と係数の関係」の式に関連していそうな気がしている。例えば以下のように1次式の積に分解された3次多項式があったとする。

$\displaystyle{ (x - \alpha_1)(x - \alpha_2)(x - \alpha_3) }$

これを展開すると以下のように各項の符号が正負交互になっているような多項式が現れる。

$\displaystyle{ x^3 - (\alpha_1 + \alpha_2 + \alpha_3)x^2 + (\alpha_1 \alpha_2 + \alpha_2 \alpha_3 + \alpha_1 \alpha_3)x - \alpha_1 \alpha_2 \alpha_3 }$

推測で物を言っているので何も証拠はないのだが、文脈によってはこちらの形式を好む人がいるのも分かるような気はする。

Conway多項式は常に存在するか？

Conway多項式は素晴らしいアイディアのように思えるが、果たしてこれは常に存在するのだろうか？つまり、任意の素数 $p$ と1以上の整数 $n$ について $C_{p, n}(x)$ が定義されるのだろうか？これについてはみんな"Endliche Körper in dem gruppentheoretischen Programmsystem GAP"という同じ論文を引用しているようで、以下に本家らしきWebページがある。
https://www2.mathematik.tu-darmstadt.de/~nickel/information.shtml

しかし、残念なことにこちらからリンクされている論文の本体ファイルはリンク切れしているようで、結局論文を見つけることはできなかった。どなたか見かけたらTwitterでもブログコメントでもよいので教えて頂けるとありがたい。

$\frac{p^n-1}{p^m-1}$ が整数であることの確認

念のため $\frac{p^n-1}{p^m-1}$ が常に整数であることを確認しておこう。 $\frac{p^n-1}{p^m-1}$ を変形して整理すると以下のようになる。

$\displaystyle { \begin{eqnarray} \frac{p^n-1}{p^m-1} &=& \frac{(p-1)\sum_{i=0}^{n-1}p^i}{(p-1)\sum_{i=0}^{m-1}p^i} \\ &=& \frac{\sum_{i=0}^{n-1}p^i}{\sum_{i=0}^{m-1}p^i} \end{eqnarray} }$

ここで、 $m$ は $n$ を割り切るので、上式は以下のように変形できる。

$\displaystyle { \begin{eqnarray} && \frac{\sum_{i=0}^{m-1}p^i + p^m\sum_{i=0}^{m-1}p^i + \cdots + p^{n-m}\sum_{i=0}^{m-1}p^i}{\sum_{i=0}^{m-1}p^i} \\ &=& \frac{\sum_{i=0}^{m-1}p^i \sum_{j=0}^{n/m-1}p^{mj}}{\sum_{i=0}^{m-1}p^i} \\ &=& \sum_{j=0}^{n/m-1}p^{mj} \end{eqnarray} }$

以上により $\frac{p^n-1}{p^m-1}$ は整数であることが分かった。

具体例で確認してみよう

例として $p=2$ のケースでいくつかConway多項式を具体的に求めてみよう。

$n=1$

$\mathbb{F}_2$ 上の1次多項式は $x$ , $x+1$ のいずれかであり、いずれも自明に既約である。ただし、原始多項式になっているのは $x+1$ のみである。1より小さい正の整数はないのでSageの条件3はスキップできる。また、今は候補となっている多項式が $x+1$ のみなので条件4もクリアできる。

以上により $C_{2,1}(x)=x+1$ である。

なお、Sage版の定義における条件4で辞書順に並び替えるときの形式に従うために、本当は符号を交互にすべきである。しかし、標数2であれば符号はどちらでもよいし、単に私が混乱するので全ての項の符号は正としておく。

$n=2$

$\mathbb{F}_2$ 上の2次既約多項式は $x^2+x+1$ のみである。これが原始多項式であることを確かめるために、Sage版の定義に従って商体 $\mathbb{F}_p[x]/(x^2+x+1)$ において $x \bmod x^2+x+1$ が乗法群を生成することを直接的に確認してみよう。

$\displaystyle{ \begin{eqnarray} x^1 &=& x \\ x^2 &=& (x^2+x+1)+x+1 \equiv x+1 \pmod{x^2+x+1} \\ x^3 &=& (x^2+x+1)(x+1)+1 \equiv 1 \pmod{x^2+x+1} \end{eqnarray} }$

ということで確かに乗法群 $\mathbb{F}_4^{\times}$ を生成することが分かった。

Sage版定義の条件3について、 $m$ の取り得る値は1のみである。このとき $\left( x \bmod f_n \right)^{\frac{p^n-1}{p^m-1}}$ は以下のようになる。

$\displaystyle{ \begin{eqnarray} \left( x \bmod x^2+x+1 \right)^{\frac{2^2-1}{2-1}} &=& \left( x \bmod x^2+x+1 \right)^{3} \\ &=& 1 \end{eqnarray} }$

1の最小多項式は $x+1$ なので、確かに $C_{2,1}(x)$ と一致している。

最後に辞書順で一番小さいものを選べば良いわけだが、今回は候補が1つしかないのでこのステップはスキップできる。

以上により、 $C_{2,2}(x) = x^2+x+1$ であることが分かった。

$n=3$

$\mathbb{F}_2$ 上の3次既約多項式は $x^3 + x + 1$ , $x^3 + x^2 + 1$ の2つである。まずはこれらが原始多項式であることを確かめたいが、愚直にやるのは面倒になったのでSageで確認してみる。

sage: R = PolynomialRing(GF(2),'x')
sage: x = R.gen()
sage: (x^3 + x + 1).is_primitive()
True
sage: (x^3 + x^2 + 1).is_primitive()
True

ということでいずれも原始多項式であることが分かった。

Sage版定義の条件3について、 $m$ の取り得る値は1のみである。このとき $\left( x \bmod x^3 + x + 1 \right)^{\frac{p^n-1}{p^m-1}}$ は以下のようになる。

$\displaystyle{ \begin{eqnarray} \left( x \bmod x^3 + x + 1 \right)^{\frac{2^3-1}{2-1}} &=& \left( x \bmod x^3 + x + 1 \right)^{7} \\ &=& 1 \end{eqnarray} }$

1の最小多項式は $x+1$ なので、確かに $C_{2,1}(x)$ と一致している。

また、 $\left( x \bmod x^3 + x^2 + 1 \right)^{\frac{p^n-1}{p^m-1}}$ は以下のようになる。

$\displaystyle{ \begin{eqnarray} \left( x \bmod x^3 + x ^2+ 1 \right)^{\frac{2^3-1}{2-1}} &=& \left( x \bmod x^3 + x^2 + 1 \right)^{7} \\ &=& 1 \end{eqnarray} }$

これも先ほどと同様に最小多項式が $C_{2,1}(x)$ と一致している。

というわけで、今回は辞書順に並べて最小のものを選ぶ必要がある。 $x^3 + x + 1$ の方が順序が小さいので、結局 $C_{2,3}(x)=x^3 + x + 1$ となる。

$n=4$

$\mathbb{F}_2$ 上の4次既約多項式は $x^4 + x + 1$ , $x^4 + x^3 + 1$ , $x^4 + x^3 + x^2 + x + 1$ の3つである。まずはSageを使ってこれらが原始多項式かどうか確かめる。

sage: R = PolynomialRing(GF(2),'x')
sage: x = R.gen()
sage: (x^4 + x + 1).is_primitive()
True
sage: (x^4 + x^3 + 1).is_primitive()
True
sage: (x^4 + x^3 + x^2 + x + 1).is_primitive()
False

ということで $x^4 + x + 1$ , $x^4 + x^3 + 1$ は原始多項式であることが分かった。

Sage版定義の条件3について、 $m$ の取り得る値として今回は1, 2の2つがある。 $n=3$ のケースを計算してみて分かったが、 $m=1$ のときは $\frac{p^n-1}{p^m-1} = p^{n-1}$ となるため、 $x$ が原始根であることより $\left( x \bmod f \right)^{p^n-1}$ ( $f$ はConway多項式の候補となる多項式) の値は必ず1になる。1の最小多項式は $C_{2,1}(x)$ なので、 $m=1$ については条件を満たす。

$m=2$ のケースについて、まずは $x^4 + x + 1$ が条件3を満たすか確かめてみる。

このとき $\left( x \bmod x^4 + x + 1 \right)^{\frac{p^n-1}{p^m-1}}$ は以下のようになる。

$\displaystyle{ \begin{eqnarray} \left( x \bmod x^4 + x + 1 \right)^{\frac{2^4-1}{2^2-1}} &=& \left( x \bmod x^4 + x + 1 \right)^{5} \\ &=& x^2 + x \end{eqnarray} }$

$x^2 + x$ の最小多項式は（ややこしいので変数を $X$ とすると） $X^2+X+1$ となる。具体的に $\mathbb{F}_2[x]/(x^4+x+1)$ 上で因数分解すると $(X - (x^2 + x))(X - (x^2 + x + 1))$ となる。これは $C_{2, 2}(x)$ に等しいので条件を満たす。

次に $x^4 + x^3 + 1$ が条件3を満たすか確かめてみる。

このとき $\left( x \bmod x^4 + x^3 + 1 \right)^{\frac{p^n-1}{p^m-1}}$ は以下のようになる。

$\displaystyle{ \left( x \bmod x^4 + x^3 + 1 \right)^{5} = x^3 + x + 1 }$

$x^3 + x + 1$ の最小多項式は（やはり変数を $X$ とすると） $X^2+X+1$ となる。具体的に $\mathbb{F}_2[x]/(x^4+x^3+1)$ 上で因数分解すると $(X - (x^3 + x + 1))(X - (x^3 + x))$ となる。これは $C_{2, 2}(x)$ に等しいので条件を満たす。

というわけで、今回は辞書順に並べて最小のものを選ぶ必要がある。 $x^3 + x + 1$ の方が順序が小さいので、結局 $C_{2,4}(x)=x^3 + x + 1$ となる。

Sageによる確認

以上、いくつか具体例を計算してみたが、ぶっちゃけこれ本当に合っているのか？という気持ちは拭えない。というわけでSageでも計算してみた。

sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
sage: PCL = PseudoConwayLattice(2, use_database=True)
sage: PCL.polynomial(1)
x + 1
sage: PCL.polynomial(2)
x^2 + x + 1
sage: PCL.polynomial(3)
x^3 + x + 1
sage: PCL.polynomial(4)
x^4 + x + 1

計算方法はSageのドキュメント[2]を参照しつつ、use_databaseオプションだけTrueにした。これは実際にConway多項式を計算するのではなく、Sage内部に持っているデータベースを使用するというオプションである。

詳細は後述するが、SageでConway多項式を計算するときは、本物のConway多項式ではなくpseudo Conway polynomialというものを計算しているらしい。一方、データベースを使用する場合は本物を返してくれるようにドキュメントから読み取れる。次数が4くらいまでであればデータベースに入っているだろうと想定して、ここではuse_databaseをTrueにした。

まあ細かいことはさておき、私が具体例のところで出した結果と一致することが分かった。

Sageが持つConway多項式のデータベースを直接確認しよう

※この章は数学的な学びは全くないので読み飛ばしても構わない。

「次数が4くらいまでであればデータベースに入っているだろう」と言ってはみたが、「本当に？」と問われると反論できないので、念のためSageのソースコードを確認した。どうやらデータベースの実体はconway_polynomials.pという不思議な拡張子のファイルらしい。
https://github.com/sagemath/sage/blob/9.8/src/sage/features/databases.py#L39

locateコマンドでファイルパスを突き止めて中身を見てみたが、どうもバイナリファイルになっているようで内容の解釈ができなかった。

$ hexdump -n 128 -C /usr/share/sagemath/conway_polynomials/conway_polynomials.p
00000000  80 02 7d 71 00 28 4b 02  7d 71 01 28 4b 01 4b 01  |..}q.(K.}q.(K.K.|
00000010  4b 01 86 71 02 4b 02 4b  01 4b 01 4b 01 87 71 03  |K..q.K.K.K.K..q.|
00000020  4b 03 28 4b 01 4b 01 4b  00 4b 01 74 71 04 4b 04  |K.(K.K.K.K.tq.K.|
00000030  28 4b 01 4b 01 4b 00 4b  00 4b 01 74 71 05 4b 05  |(K.K.K.K.K.tq.K.|
00000040  28 4b 01 4b 00 4b 01 4b  00 4b 00 4b 01 74 71 06  |(K.K.K.K.K.K.tq.|
00000050  4b 06 28 4b 01 4b 01 4b  00 4b 01 4b 01 4b 00 4b  |K.(K.K.K.K.K.K.K|
00000060  01 74 71 07 4b 07 28 4b  01 4b 01 4b 00 4b 00 4b  |.tq.K.(K.K.K.K.K|
00000070  00 4b 00 4b 00 4b 01 74  71 08 4b 08 28 4b 01 4b  |.K.K.K.tq.K.(K.K|
00000080

仕方がないのでプログラムからデータベースの中を覗いてみることにした。ソースコードの以下のあたりを読んで、実際に登録されているデータベースの情報を引っ張りだしてみた。
https://github.com/sagemath/sage/blob/9.8/src/sage/databases/conway.py#L179-L210

sage: C = sage.databases.conway.ConwayPolynomials()
sage: C.polynomial(2, 1)
(1, 1)
sage: C.polynomial(2, 2)
(1, 1, 1)
sage: C.polynomial(2, 3)
(1, 1, 0, 1)
sage: C.polynomial(2, 4)
(1, 1, 0, 0, 1)

出力に出てくる数字は左から順に0次の項、1次の項・・・という風に解釈すればよい。なお、データベースに存在しないものを取得しようとすると以下のようにRuntimeErrorになる。

sage: C.polynomial(2, 1000)
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
/usr/lib/python3/dist-packages/sage/databases/conway.py in polynomial(self, p, n)
    221         try:
--> 222             return self[p, n]
    223         except KeyError:

・・・長いので割愛・・・

RuntimeError: Conway polynomial over F_2 of degree 1000 not in database.

もしくはドキュメントに書かれている以下の関数を使ってもデータベースへの登録状況が分かるようだ。結果がbool型で得られるので、実用上はこちらの関数の方が使い勝手が良いだろう。
https://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/conway_polynomials.html#sage.rings.finite_rings.conway_polynomials.exists_conway_polynomial

いずれにせよ、標数2の場合は少なくとも4次のConway多項式まではSageのデータベースに登録されていることが分かった。

Conway多項式を用いた有限体の表現

さて、話が発散しかかったが、結局言いたかったのは有限体を生成する際に使用する既約多項式としてはConway多項式を使えばよいということである。例として $\mathbb{F}_{16}$ およびその部分体 $\mathbb{F}_4$ がどのように表現されるかを考えてみよう。

まず、 $C_{2, 4}(x)$ を用いて $\mathbb{F}_{16}$ を $\mathbb{F}_2[x]/(C_{2, 4}(x))$ として表現する。 $C_{2, 4}(x)$ は4次原始多項式なので、その根は $\mathbb{F}_{16}^{\times}$ を生成する。Conway多項式の性質より $x^5 \bmod C_{2, 4}(x)$ は $C_{2, 2}(x)$ の根であり、これも原始多項式なので $\mathbb{F}_4^{\times}$ を生成する。つまり、 $1,\ x^5,\ x^{10}$ が $\mathbb{F}_4^{\times}$ と同型になる。 $0 \in \mathbb{F}_4$ は $0 \in \mathbb{F}_{16}$ に対応させればよい。これにより、 $\mathbb{F}_{16}$ が具体的に表現されるのに加えて、部分体である $\mathbb{F}_{4}$ の表現も具体的に決まることが分かる。

Pseudo Conway polynomial

Sageのドキュメントを見ると、どうやらSageでは辞書順の条件は諦めているらしい。正確な理由は分からないが、恐らく全ての候補を見つけて辞書順に並び替えるという操作の計算量が大きくなるのを嫌ったのではないかと推測している。Sageではこの辞書順の条件のみを外したConway多項式もどきのことをpseudo Conway polynomialと呼んでいるようだ[2]。

試しにuse_database=Falseとしてpseudo Conway polynomialを計算してみると、4次多項式についてはSage版定義の条件1～3までで選ばれた他の多項式が出力された。

sage: from sage.rings.finite_rings.conway_polynomials import PseudoConwayLattice
sage: PCL = PseudoConwayLattice(2, use_database=False)
sage: PCL.polynomial(3)
x^3 + x + 1
sage: PCL.polynomial(4)
x^4 + x^3 + 1