フォージェールのF4およびF5アルゴリズム

数式処理において、ジャン＝シャルル・フォージェールによるフォージェールF4アルゴリズムは、多変数多項式環のイデアルのグロブナー基底を計算します。このアルゴリズムはブッフベルガーアルゴリズムと同じ数学的原理を用いますが、一般的に疎行列を作成し、高速線形代数を用いて並列に縮約を行うことで、多くの正規形を一度に計算します。

フォージェールF5アルゴリズムは、まずイデアルの生成多項式のペアのグロブナー基底を計算します。次に、この基底を使用して、次のより大きな基底の生成行列の初期サイズを縮小します。

G _{prev が}既に計算された Gröbner 基底 ( f ₂ , …, f _m ) であり、( f ₁ )  + G _prevの Gröbner 基底を計算したい場合は、行がm f ₁である行列を構築します。ここで、mはG _prevの要素の先頭項で割り切れない単項式です。  

この戦略により、アルゴリズムはフォージェールが多項式のシグネチャと呼ぶものに基づいた2つの新しい基準を適用できるようになります。これらの基準のおかげで、アルゴリズムは、正則数列と呼ばれる多くの興味深い多項式系に対して、単一の多項式をゼロに単純化することなく（これは、グレブナー基底を計算するアルゴリズムにおいて最も時間のかかる操作です）、グレブナー基底を計算できます。また、多数の非正則数列に対しても非常に効果的です。

フォージェールF4アルゴリズムが実装されています

• FGbでは、Faugère 自身の実装には、 C/C++やMapleから使用するためのインターフェースが含まれています。
• Maple 数式処理システムでは、関数Groebner[gbasis]のオプションmethod=fgbとして機能します。
• Magmaコンピュータ代数システムでは、
• SageMathコンピュータ代数システムでは、

Faugère F5 アルゴリズムの研究バージョンは、

• SINGULARコンピュータ代数システム; ^{[ 1 ]}
• SageMathコンピュータ代数システム。
• SymPy Pythonパッケージ内。^{[ 2 ]}

以前は解決不可能だった「巡回10」問題はF5によって解決され、暗号化に関連する多くのシステム（例えばHFEやC ^*）も同様に解決されました。

• Faugère, J.-C. (1999年6月). 「Gröbner基底(F ₄ )を計算するための新しい効率的なアルゴリズム」 (PDF) . Journal of Pure and Applied Algebra . 139 (1): 61– 88. doi : 10.1016/S0022-4049(99)00005-5 . ISSN 0022-4049 . 
• Faugère, J.-C. (2002年7月). 「ゼロへの還元なしにグレブナー基底を計算する新しい効率的なアルゴリズム ( F ₅ )」. 2002年国際シンポジウム「記号計算と代数計算」論文集(PDF) . ACM Press. pp. 75–83 . CiteSeerX 10.1.1.188.651 . doi : 10.1145/780506.780516 . ISBN   978-1-58113-484-1. S2CID 15833106 . 
• ステジェール・フォージェールの F5 アルゴリズムを再検討するまで(代替リンク)。数学卒業証書、ダルムシュタット工科大学顧問ヨハネス・ブッフマン、2005 年 9 月 (2007 年 4 月 27 日改訂)。利用可能な実装へのリンクを含む多くの参考資料。

• フォージェールのホームページ（追加論文のPDF版も掲載）
• F4アルゴリズムの概要。