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

Revision as of 15:37, 11 October 2013

Latest revision as of 09:34, 4 April 2025

(27 intermediate revisions by 21 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 10 ⟶ 11:

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 [[Magma computer algebra system]],

* in the [[Xcas|Giac/Xcas computer algebra sysmtem]]<ref>{{cite arXiv |last= Parisse|first= Bernard | eprint= 1309.4044|title= A probabilistic and deterministic modular algorithm for computing Groebner basis over Q |class= cs.SC | year=2013}} </ref>.

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

* as a [http://www-calfor.lip6.fr/~jcf/Software/FGb/C%20API/index.html C library].

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 [[Sage (mathematics software)|SageSageMath]] 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==

Line 35 ⟶ 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

| 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

| issnisbn = 978-1-58113-484-31

| 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.]

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

[[Category:Computer algebra]]

{{algorithm-stub}}