コンウェイ多項式（有限体）

数学において、有限体_{F p ⁿ}のコンウェイ多項式 C _{p , n}は、 F p 上の n 次数の特定の既約多項式であり、_F p nの標準表現_を^C p , n の分解体として定義するために使用できます。_{コンウェイ多項式は}、それらを最初に定義して例を計算したリチャード A. パーカーによってジョン H. コンウェイにちなんで命名されました。コンウェイ多項式は、体の表現とその部分体の表現の間でコンウェイによって提案された特定の互換性条件を満たします。これらは、異なる数学データベースとコンピュータ代数システム間での移植性を提供するコンピュータ代数において重要です。コンウェイ多項式の計算にはコストがかかるため、実際に使用するには保存する必要があります。コンウェイ多項式のデータベースは、コンピュータ代数システムGAP、^[1] Macaulay2、^[2] Magma、^[3] SageMath、^[4] Frank Lübeckのウェブサイト、^[5] Online Encyclopedia of Integer Sequences ^[6] で利用できます。

F _{p ⁿ}の元は、 a _{n −1} β ^{n −1} + … + a ₁ β + a ₀の形式の和として表すことができます。ここで、β はF _p上のn次既約多項式の根であり、a _{j は}F _pの元です。この表現における体の元の加算は、単にベクトルの加算です。同型までp ⁿ位の唯一の有限体がありますが、体の元の表現は既約多項式の選択に依存します。コンウェイ多項式は、この選択を標準化する方法です。

有限体Fの非ゼロ元は、乗法の下で巡回群を形成し、F ^*と表記されます。F _{p ⁿ}の原始元αは、 F ^* _{p ^{n を}}生成する元です。非ゼロ体の元をαのべき乗として表すと、体での乗法を効率的に実行できます。αの原始多項式は、 F _{p ⁿ}の根としてα を持つ、 F _pに係数を持つ最小次数の単項多項式です( αの最小多項式)。これは必然的に既約です。コンウェイ多項式は原始的になるように選択され、その根のそれぞれが関連する有限体の乗法群を生成します。

体F _{p ⁿ}には、 n を割り切る各mに対してF _{p ^m}と同型の一意の部分体が含まれており、これがF _{p ⁿ}のすべての部分体を説明します。n を割り切る任意のmに対して、巡回群F ^* _{p ⁿ}にはF ^* _{p ^m}と同型の部分群が含まれます 。αがF ^* _{p ⁿ}を生成する場合、この部分群を生成するαの最小のべき乗はα ^rであり、ここでr = ( p ⁿ − 1) / ( p ^m − 1)です。f _nがF _{p ⁿ}の原始多項式で根がαであり、f _{m が}F _{p ^m}の原始多項式である場合、コンウェイの定義により、 α ^{r が}f _mの根である場合にf _mとf _nは互換性があります。これにより、 f _n ( x ) がf _m ( x ^r )を割り切ることが必須になります。この互換性の概念は、一部の著者によってノルム互換性と呼ばれています。有限体のコンウェイ多項式は、その部分体のそれぞれのコンウェイ多項式と互換性を持つように選択される。このように選択することが可能であるということは、ヴェルナー・ニッケルによって証明された。^[7]

コンウェイ多項式C _{p , n は}、 nを割り切るすべてのmに対してC _{p , m}と互換性のある、F _p上のn次の辞書式最小単項原始多項式として定義されます。これはnに関する帰納的定義です。基本ケースはC _{p ,1} ( x ) = x − αです。ここで、αはF _pの辞書式最小原始要素です。使用される辞書式順序の概念は次のとおりです。

• F _pの要素は0 < 1 < 2 < … < p − 1の順序になります。
• F _p [ x ]のd次多項式は、a _d x ^d − a _{d −1} x ^{d −1} + … + (−1) ^d a ₀（項を交互に加算および減算）と記述され、単語a _d a _{d −1} … a ₀として表現されます。 2 つのd次多項式は、対応する単語の辞書式順序に従って順序付けられます。

他のすべてのモニック原始多項式よりも互換性条件を満たす 1 つのモニック原始多項式を選択する自然な数学的基準は存在しないと思われるため、コンウェイ多項式の定義で辞書式順序を強制することは慣例と見なされるべきです。

pとnの最小値に対するコンウェイ多項式C _{p、n は}、以下の表に示されています。これらはすべて、Richard Parker によって最初に計算され、Frank Luebeck の表から取得されました。計算は、代数ソフトウェアの支援を受けて、次のセクションの基本的な方法を使用して検証できます。

定義を説明するために、 F ₅上の最初の 6 つのコンウェイ多項式を計算してみましょう。定義により、コンウェイ多項式はモニック、プリミティブ（つまり既約）であり、その次数を割り切る次のコンウェイ多項式と互換性があります。以下の表は、これらの条件をそれぞれ課すことで、候補となる多項式の数が減る様子を示しています。^[8]

1次。F ₅の原始元は2 と 3 です。したがって、原始根を持つ 2 つの 1 次多項式はx − 2 = x + 3とx − 3 = x + 2となり、これは単語 12 と 13 に対応します。辞書式順序では 12 は 13 より小さいため、C _5,1 ( x ) = x + 3 となります。

2 次。(5 ² − 1) / (5 ¹ − 1) = 6なので、互換性のためにはC _{5,2 は}C _5,2 ( x ) がC _5,1 ( x ⁶ ) = x ⁶ + 3を割り切るように選ばれる必要があります。後者は、 F ₅上で既約な 3 つの 2 次多項式、つまりx ² + 2、x ² + x + 2、およびx ² + 4 x + 2に因数分解されます。これらのうち、 x ² + 2はx ⁸ − 1を割り切るため原始的ではなく、その根の位数は必要な 24 ではなく最大で 8 になります。他の 2 つは両方とも原始的であり、C _{5,2 は}2 つのうち辞書式順序が小さい方として選ばれます。ここで、x ² + x + 2 = x ² − 4 x + 2 は単語 142 に対応し、x ² + 4 x + 2 = x ² − x + 2は単語 112 に対応します。後者は辞書順では前者より小さいです。したがって、C _5,2 ( x ) = x ² + 4 x + 2です。

3 次。(5 ³ − 1) / (5 ¹ − 1) = 31なので、互換性のためにはC _5,3 ( x )がC _5,1 ( x ³¹ ) = x ³¹ + 3を割り切る必要があります。これは、1 次多項式と 10 個の原始 3 次多項式の積として因数分解されます。これらのうち、2 つには二次項がなく、x ³ + 3 x + 3 = x ³ − 0 x ² + 3 x − 2とx ³ + 4 x + 3 = x ³ − 0 x ² + 4 x − 2で、これは単語 1032 と 1042 に対応します。1032 は辞書式で 1042 より小さいので、C _5,3 ( x ) = x ³ + 3 x + 3です。

4 次。4の真約数は1と2です。(5 ⁴ − 1) / (5 ² − 1) = 26と(5 ⁴ − 1) / (5 ¹ − 1) = 156 を計算します。156 / 26 = (5 ² − 1) / (5 ² − 1) = 6であり、これは 2 次での適合条件で現れたのと同じ指数であることに注意してください。4 次では、適合性のために、C _5,4は、 C _5,4 ( x ) がC _5,2 ( x ²⁶ ) = x ⁵² + 4 x ²⁶ + 2とC _5,1 ( x ¹⁵⁶ ) = x ¹⁵⁶ + 3の両方を割り切るように選択する必要があります。ただし、 2 番目の条件は冗長です。これは、 C _{5,2 を}選択するときに課される適合条件により、 C _5,2 ( x ²⁶ ) はC _5,1 ( x ¹⁵⁶ )を割り切れることを意味します。一般に、合成次数dの場合、同じ推論により、 dの最大真約数、つまりd / pの形式の約数のみを考慮する必要があることが示されます。ここで、 pはdの素約数です。 C _5,2 ( x ²⁶ )には 13 個の因数があり、すべて次数 4 です。1 つを除いてすべて原始因数です。原始因数のうち、x ⁴ + 4 x ² + 4 x + 2は辞書式最小です。

5 次。計算は 2 次および 3 次で行われたものと同様です: (5 ⁵ − 1) / (5 ¹ − 1) = 781 ; C _5,1 ( x ⁷⁸¹ ) = x ⁷⁸¹ + 3には 1 次因子が 1 つと 5 次因子が 156 個あり、そのうち 140 個は原始因子です。辞書順で最小の原始因子はx ⁵ + 4 x + 3です。

6 次。4次に関する上記の議論を考慮すると、考慮する必要がある 2 つの互換性条件は、C _5,6 ( x )がC _5,2 ( x ⁶⁵¹ ) = x ¹³⁰² + 4 x ⁶⁵¹ + 2とC _5,3 ( x ¹²⁶ ) = x ³⁷⁸ + 3 x ¹²⁶ + 3を割り切れることです。したがって、それらの最大公約数x ¹²⁶ + x ¹⁰⁵ + 2 x ⁸⁴ + 3 x ⁴² + 2を割り切れる必要があります。これは、21 個の 6 次多項式に因数分解され、そのうち 18 個は原始多項式です。これらのうち辞書順で最小のものは、x ⁶ + x ⁴ + 4 x ³ + x ² + 2です。

ヒースとローアは、総当たり探索よりも効率的なコンウェイ多項式を計算するアルゴリズムを開発しました。^[9] リューベックは^[5]、彼らのアルゴリズムはパーカーの方法の再発見であると述べています。

• Holt, Derek F.; Eick, Bettina; O'Brien, Eamonn A. (2005)、計算群論ハンドブック、離散数学とその応用、第24巻、CRC Press、ISBN 978-1-58488-372-2