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

Revision as of 22:48, 19 November 2020

Latest revision as of 09:34, 4 April 2025

(7 intermediate revisions by 6 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 19 ⟶ 20:

* 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 41 ⟶ 42:

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

Line 48 ⟶ 50:

| last = Faugère

| first = J.-C.

| journaltitle = Proceedings of the 2002 Internationalinternational Symposiumsymposium on Symbolic and Algebraicalgebraic Computation (ISSAC)computation

| 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

Line 57 ⟶ 59:

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

| citeseerx = 10.1.1.188.651

| s2cid = 15833106

}}

}}

* 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}}