Content deleted Content added
mNo edit summary |
No edit summary |
||
Line 1:
In [[computer algebra]], the '''Faugère F4 algorithm''', by [[Jean-Charles Faugère]], computes the [[Gröbner basis]] of an [[ideal (ring theory)|ideal]] of a multivariate [[polynomial ring]]. The algorithm uses the same mathematical principles as the [[Buchberger algorithm]], but computes many normal forms in one go by forming a generally [[sparse matrix]] and using fast linear algebra to do the reductions in parallel.
The Faugère F4 algorithm is implemented ▼
* as a [http://fgbrs.lip6.fr/jcf/Software/ package FGb] for the [[Maple computer algebra system]]▼
* in the [[Magma computer algebra system]]▼
The '''Faugère F5 algorithm''' first calculates the Gröbner basis of a pair of generator polynomials of the ideal. Then it uses this basis to reduce the size of the initial matrices of generators for the next larger basis:
Line 10 ⟶ 6:
</blockquote>
This strategy allows the algorithm to apply two new criteria based on what Faugère calls ''signatures'' of polynomials. Thanks to these criteria, the algorithm can compute Gröbner bases for a large class of interesting polynomial systems, called ''regular sequences'', without ever simplifying a single polynomial to zero--the most time-consuming operation in algorithms that compute Gröbner bases.
== Implementations ==
▲The Faugère F4 algorithm is implemented
▲* as a [http://fgbrs.lip6.fr/jcf/Software/ package FGb] for the [[Maple computer algebra system]]
▲* in the [[Magma computer algebra system]]
== Applications ==
The previously intractable "cyclic 10" problem was solved by F5, as were a number of systems related to cryptography; for example [[Hidden Field Equations|HFE]] and C<sup>*</sup>.
| |||