ベルレカンプのアルゴリズム

数学、特に計算代数において、ベルレカンプのアルゴリズムは有限体（ガロア体とも呼ばれる）上の多項式を因数分解するよく知られた手法である。このアルゴリズムは主に行列縮小と多項式GCD計算から構成される。これは1967年にエルウィン・ベルレカンプによって発明された。 1981年にカンター・ザッセンハウスのアルゴリズムが発明されるまで、このアルゴリズムは問題を解くための主要なアルゴリズムであった。 現在、このアルゴリズムは多くのよく知られたコンピュータ代数システムに実装されている。

Berlekamp のアルゴリズムは、有限体上の係数を持つ次数の平方のない多項式 (つまり、重複する因数を持たない多項式)を入力として受け取り、を割り切れる同じ体上の係数を持つ多項式を出力します。次に、アルゴリズムをこれらの約数と後続の約数に再帰的に適用し、 を既約多項式のべき乗に分解します(有限体上の多項式環は一意の因数分解領域であることを思い出してください)。 ${\displaystyle f(x)}$${\displaystyle n}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle g(x)}$${\displaystyle g(x)}$${\displaystyle f(x)}$${\displaystyle f(x)}$

のすべての可能な因数は因数環内に含まれる。${\displaystyle f(x)}$

${\displaystyle R={\frac {\mathbb {F} _{q}[x]}{\langle f(x)\rangle }}.}$

このアルゴリズムは、合同性を満たす多項式に焦点を当てています。 ${\displaystyle g(x)\in R}$

${\displaystyle g(x)^{q}\equiv g(x){\pmod {f(x)}}.\,}$

これらの多項式は、 R の部分代数（上の - 次元ベクトル空間とみなすことができる）を形成し、ベルレカンプ部分代数と呼ばれる。ベルレカンプ部分代数は、それに含まれる 多項式が次式を満たすため興味深い。${\displaystyle n}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle g(x)}$

${\displaystyle f(x)=\prod _{s\in \mathbb {F} _{q}}\gcd(f(x),g(x)-s).}$

一般に、上記の積の GCD のすべてが の非自明な因数になるわけではありませんが、いくつかは となり、求める因数を提供します。 ${\displaystyle f(x)}$

ベルレカンプのアルゴリズムは、ベルレカンプ部分代数の基底を計算することによって、上記の結果に使用するのに適した多項式を見つけます。これは、ベルレカンプ部分代数が実際には上の特定の行列の核であり、多項式のいわゆるベルレカンプ行列 から導かれるという観察によって実現されます。 の場合、 はを法として簡約した の - 乗項の係数です。つまり、 ${\displaystyle g(x)}$${\displaystyle n\times n}$${\displaystyle \mathbb {F} _{q}}$${\displaystyle {\mathcal {Q}}}$${\displaystyle {\mathcal {Q}}=[q_{i,j}]}$${\displaystyle q_{i,j}}$${\displaystyle j}$${\displaystyle x^{iq}}$${\displaystyle f(x)}$

${\displaystyle x^{iq}\equiv q_{i,n-1}x^{n-1}+q_{i,n-2}x^{n-2}+\ldots +q_{i,0}{\pmod {f(x)}}.\,}$

ある多項式について、次のように言います。 ${\displaystyle g(x)\in R}$

${\displaystyle g(x)=g_{n-1}x^{n-1}+g_{n-2}x^{n-2}+\ldots +g_{0},\,}$

行ベクトルを関連付けることができます。

${\displaystyle g=(g_{0},g_{1},\ldots ,g_{n-1}).\,}$

同様に、行ベクトルがを法とする の簡約に対応することは比較的簡単にわかります。したがって、多項式がベルレカンプ部分代数に含まれるのは、 （ここでは単位行列）の場合のみ、つまり のヌル空間に含まれる場合のみとなります。 ${\displaystyle g{\mathcal {Q}}}$${\displaystyle g(x)^{q}}$${\displaystyle f(x)}$${\displaystyle g(x)\in R}$${\displaystyle g({\mathcal {Q}}-I)=0}$${\displaystyle I}$${\displaystyle n\times n}$ ${\displaystyle {\mathcal {Q}}-I}$

行列を計算し、それを簡約された行階段形式に簡約し、ヌル空間の基底を簡単に読み取ることによって、ベルレカンプ部分代数の基底を見つけ、その中の多項式を構築することができます。次に、非自明な因子が見つかるまで、上記の形式の GCD を連続的に計算する必要があります。体上の多項式環はユークリッド領域であるため、ユークリッドのアルゴリズムを使用してこれらの GCD を計算できます。 ${\displaystyle {\mathcal {Q}}-I}$${\displaystyle g(x)}$

抽象代数を使うと、ベルレカンプのアルゴリズムの背後にある考え方が概念的に明確になります。有限体 を、ある素数に対して として表します。すべての可能な p 乗根を取り、その導関数で gcd を計算することで、 が平方数でないと仮定できます。 ${\textstyle \mathbb {F} _{q}}$${\textstyle q=p^{m}}$${\textstyle p}$${\textstyle \mathbb {F} _{p}[y]/(g(y))}$${\textstyle f(x)\in \mathbb {F} _{q}[x]}$

ここで、 が既約な因数分解であると仮定します。すると、中国剰余定理によって与えられる環同型 が得られます。重要な観察は、フロベニウスの自己同型がと可換であるため、 と表記すると、同型 に制限されるということです。有限体論により、 は常にその体拡大の主部分体です。したがって、が元を持つ のは、 が既約な場合のみと なります。 ${\textstyle f(x)=f_{1}(x)\ldots f_{n}(x)}$${\textstyle \sigma :\mathbb {F} _{q}[x]/(f(x))\to \prod _{i}\mathbb {F} _{q}[x]/(f_{i}(x))}$${\textstyle x\to x^{p}}$${\textstyle \sigma }$${\textstyle {\text{Fix}}_{p}(R)=\{f\in R:f^{p}=f\}}$${\textstyle \sigma }$${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\to \prod _{i=1}^{n}{\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f_{i}(x)))}$${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f_{i}(x)))}$${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))}$${\textstyle p}$${\textstyle f(x)}$

さらに、フロベニウスの自己同型が- 線型であるという事実を利用して、固定集合を計算することができます。つまり、 は- 部分空間であり、それがフロベニウスによって固定される場合に限って満たされる多項式の係数に関する線型方程式を計算して確立することにより、多項式環でその明示的な基底を計算できることに注目してください。この時点で、効率的に計算可能な既約基準が得られ、残りの分析では、これを使用して因数を見つける方法を示しています。 ${\textstyle \mathbb {F} _{p}}$${\textstyle {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))}$${\textstyle \mathbb {F} _{p}}$${\textstyle \mathbb {F} _{p}[x,y]/(f,g)}$${\textstyle (x^{i}y^{j})^{p}}$${\textstyle x,y}$

アルゴリズムは、次の 2 つのケースに分類されます。

• が小さい場合、 任意の を構築することができ 、いくつかの に対してが存在し、およびとなることがわかります。このような はと共通の非自明な因数を持ち、これは gcd を介して計算できます。が小さいため、すべての可能な を循環的に調べることができます。${\textstyle p}$${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/(f(x)))\setminus \mathbb {F} _{p}}$${\textstyle a\in \mathbb {F} _{p}}$${\textstyle i,j}$${\textstyle g-a=0\mod f_{i}}$${\textstyle g-a\not =0\mod f_{j}}$${\textstyle g-a}$${\textstyle f(x)}$${\textstyle p}$${\textstyle a}$
• 必然的に奇数となる大きな素数の場合、 のランダムな非ゼロ元が確率 で平方値になるという事実と、写像 が非ゼロ平方値の集合を に、非平方値の集合を に写像するという事実を利用できます。したがって、ランダムな元 を取ると、 は と共通の非自明な因数を持つ確率が高くなります。${\textstyle \mathbb {F} _{p}^{*}}$${\textstyle 1/2}$${\textstyle x\to x^{\frac {p-1}{2}}}$${\textstyle 1}$${\textstyle -1}$${\textstyle g\in {\text{Fix}}_{p}(\mathbb {F} _{q}[x]/f(x))}$${\textstyle g^{\frac {p-1}{2}}-1}$${\textstyle f(x)}$

詳細については、以下を参照してください。^[1]

Berlekamp アルゴリズムの重要な応用の 1 つは、有限体 上の離散対数の計算です。ここで、 は素数であり、 です。離散対数の計算は、公開鍵暗号化とエラー制御コーディングにおける重要な問題です。有限体の場合、最も高速な既知の方法は、体元の因数分解を伴うインデックス計算法です。通常の方法、つまり、次数の既約多項式を法として簡約された、基底体 上の多項式として体を表す場合、これは Berlekamp アルゴリズムによって提供されるように、単純に多項式因数分解です。 ${\displaystyle \mathbb {F} _{p^{n}}}$${\displaystyle p}$${\displaystyle n\geq 2}$${\displaystyle \mathbb {F} _{p^{n}}}$${\displaystyle \mathbb {F} _{p}}$${\displaystyle n}$

Berlekampのアルゴリズムは、factormodコマンドを使用してPARI/GPパッケージでアクセスでき、WolframAlpha [1]のWebサイトでもアクセスできます。

• 多項式因数分解
• 有限体上の多項式の因数分解と既約性テスト
• カンター・ザッセンハウスアルゴリズム

• Berlekamp, Elwyn R. (1967). 「有限体上の多項式の因数分解」. Bell System Technical Journal . 46 (8): 1853–1859. doi :10.1002/j.1538-7305.1967.tb03174.x. MR  0219231.BSTJ 後に再出版：Berlekamp, Elwyn R. (1968). Algebraic Coding Theory . McGraw Hill. ISBN 0-89412-063-8。
• Knuth, Donald E (1997)。「4.6.2 多項式の因数分解」。半数値アルゴリズム。コンピュータプログラミングの技法。第 2 巻 (第 3 版)。マサチューセッツ州レディング: Addison-Wesley。pp. 439–461, 678–691。ISBN 0-201-89684-2。