Faugère's F4 and F5 algorithms: Difference between revisions

Revision as of 23:13, 27 April 2011

Latest revision as of 09:34, 4 April 2025

(40 intermediate revisions by 23 users not shown)

Line 1:

{{Short description|Algorithms for computing Gröbner bases}}

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.

Line 5 ⟶ 6:

If ''G''_prev is an already computed Gröbner basis (''f''₂, …, ''f''_''m'') and we want to compute a Gröbner basis of (''f''₁) + ''G''_prev then we will construct matrices whose rows are ''m'' ''f''₁ such that ''m'' is a monomial not divisible by the leading term of an element of ''G''_prev.

</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 sequencessequence]]s'', without ever simplifying a single polynomial to zero--thezero—the most time-consuming operation in algorithms that compute Gröbner bases. It is also very effective for a large number of non-regular sequences.

== Implementations ==

The Faugère F4 algorithm is implemented

* as ain [http://www-calforpolsys.lip6.fr/~jcf/Software/FGb package/index.html FGb], for theFaugère's [[Mapleown computerimplementation, algebrawhich system]].includes Thisinterfaces packagefor isusing includedit infrom [[C/C++]] or [[Maple (software)|Maple]] distribution as the option '''method=fgb''' of function '''Groebner[gbasis]'''.,

* in the [[MagmaMaple computer algebra system]], as the option '''method=fgb''' of function '''Groebner[gbasis]'''

* in the [[SINGULAR]]Magma computer algebra system]],

* in the [[SageMath]] computer algebra system,

Study versions of the Faugère F5 algorithm is implemented in{{citation needed|date=February 2013}}

* the [[SINGULAR]] computer algebra system;<ref>{{cite arXiv |last=Eder |first=Christian |eprint=0804.2033 |title=On The Criteria Of The F5 Algorithm |class= math.AC|year=2008 }}</ref>

* the [[SageMath]] computer algebra system.

* in [[SymPy]] [[Python (programming language)|Python]] package.<ref>{{Cite web|url=https://docs.sympy.org/latest/modules/polys/internals.html#groebner-basis-algorithms|title=Internals of the Polynomial Manipulation Module — SymPy 1.9 documentation}}</ref>

== Applications ==

The previously intractable "cyclic 10" problem was solved by F5,{{cn|date=November 2020}} as were a number of systems related to cryptography; for example [[Hidden Field Equations|HFE]] and C^*.{{cn|date=November 2020}}

==References==

{{Reflist}}

* {{cite journal

| last = Faugère

Line 27 ⟶ 38:

| issue = 1

| pages = 61–88

| publisher = Elsevier Science

| date = June 1999

| url = http://www-calforpolsys.lip6.fr/~jcf/Papers/F99a.pdf

| doi = 10.1016/S0022-4049(99)00005-5

| idissn = {{ISSN|0022-4049}}

| doi-access = free

}}

}}

<!--

*[http://citeseer.ist.psu.edu/context/1885943/0 Reference to paper by Faugère describing the F4 algorithm]

-->

* {{cite journalbook

| last = Faugère

| first = J.-C.

| journaltitle = Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC)

| titlechapter = A new efficient algorithm for computing Gröbner bases without reduction to zero ( ''F'' ₅ )

| journal = Proceedings of the 2002 international symposium on Symbolic and algebraic computation (ISSAC)

| pages = 75–83

| publisher = ACM Press

| date = July 2002

| url = http://www-calforpolsys.lip6.fr/~jcf/Papers/F02a.pdf

| doi = 10.1145/780506.780516

| idisbn = {{ISSN|978-1-58113-484-3}}1

| citeseerx = 10.1.1.188.651

}}

| s2cid = 15833106

* Till Stegers [http://wwwcsif.cs.ucdavis.edu/~stegers/diplom_stegers.pdf Faugere's F5 Algorithm Revisited] ([http://eprint.iacr.org/2006/404 alternative link]). Diplom-Mathematiker Thesis, advisor Johannes Buchmann, Technische Universität Darmstadt, September 2005 (revised April 27, 2007). Many references, including links to available implementations.

}}

* Till Stegers [https://web.archive.org/web/20081202150316/http://wwwcsif.cs.ucdavis.edu/~stegers/diplom_stegers.pdf FaugereFaugère's F5 Algorithm Revisited] ([http://eprint.iacr.org/2006/404 alternative link]). Diplom-Mathematiker Thesis, advisor Johannes Buchmann, Technische Universität Darmstadt, September 2005 (revised April 27, 2007). Many references, including links to available implementations.

==External links==

* [http://www-calforpolsys.lip6.fr/~jcf/ Faugère's home page] (includes pdf reprints of additional papers)

* [httphttps://www.broune.com/paperss/f4.pdf An introduction to the F4 algorithm.]

{{algorithm-stub}}

{{DEFAULTSORT:Faugere's F4 and F5 algorithms}}

[[Category:Computer algebra]]