Factorization of polynomials over finite fields とは

数学とコンピュータ代数では、多項式の因数分解は、それを既約因子の積に分解することからなる。この分解は理論的に可能であり、任意のフィールドの係数を有する多項式に対して一意であるが、むしろアルゴリズムの手段による分解の計算を可能にするために係数のフィールドに対する強い制限が必要である。実際には、アルゴリズムは有限体内の係数を有する多項式、有理数の分野またはそれらの1つの有限生成された場の拡張でのみ設計されている。
この記事の主題である有限体上の単変量多項式の因数分解の場合は、特に重要である。なぜなら、十分に効率的に実行されるすべてのアルゴリズム(有理数に対する多変量多項式の場合を含む)は、このケースに問題を減らしてください(多項式分解を参照)。また、符号理論(巡回冗長符号とBCH符号)、暗号(楕円曲線による公開鍵暗号)、計算数理論​​などの有限体の様々な応用にも興味深い。
多変量多項式の単変量多項式への分解は、有限体の係数の場合に特段の特質を持たないため、この記事では変数が1つの多項式のみを考慮する。