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

Revision as of 07:10, 28 September 2017

Latest revision as of 09:34, 4 April 2025

(14 intermediate revisions by 11 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 11 ⟶ 12:

The Faugère F4 algorithm is implemented

* in [http://www-polsys.lip6.fr/~jcf/FGb/index.html FGb], Faugère's own implementation, which includes interfaces for using it from [[C/C++]] or [[Maple (software)|Maple]],

* in [[Maple computer algebra system]], as the option '''method=fgb''' of function '''Groebner[gbasis]''' (this is an older version of FGb, with limitations of the size of the problems that can be solved),

* in the [[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==

Line 35 ⟶ 38:

| issue = 1

| pages = 61–88

| publisher = Elsevier Science

| date = June 1999

| url = http://www-polsys.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-polsys.lip6.fr/~jcf/Papers/F02a.pdf

| doi = 10.1145/780506.780516

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

| citeseerx = 10.1.1.188.651

}}

| s2cid = 15833106

* Till Stegers [http://wwwcsif.cs.ucdavis.edu/~stegers/diplom_stegers.pdf Faugè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.

}}

* Till Stegers [https://web.archive.org/web/20081202150316/http://wwwcsif.cs.ucdavis.edu/~stegers/diplom_stegers.pdf Faugè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-polsys.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}}