Faugere's F5 Algorithm Revisited

Till Stegers

Paper 2006/404

Faugere's F5 Algorithm Revisited

Till Stegers

Abstract

We present and analyze the F5 algorithm for computing Groebner bases. On the practical side, we correct minor errors in Faugere's pseudo code, and report our experiences implementing the -- to our knowledge -- first working public version of F5. While not designed for efficiency, it will doubtless be useful to anybody implementing or experimenting with F5. In addition, we list some experimental results, hinting that the version of F5 presented in Faugere's original paper can be considered as more or less naive, and that Faugere's actual implementations are a lot more sophisticated. We also suggest further improvements to the F5 algorithm and point out some problems we encountered when attempting to merge F4 and F5 to an "F4.5" algorithm. On the theoretical side, we slightly refine Faugere's theorem that it suffices to consider all normalized critical pairs, and give the first full proof, completing his sketches. We strive to present a more accessible account of the termination and correctness proofs of F5. Unfortunately, we still rely on a conjecture about the correctness of certain optimizations. Finally, we suggest directions of future research on F5.

Note: Fixed mistake in F5 pseudocode (reported by John Perry).

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Diplom thesis at TU Darmstadt, Germany
Keywords: Groebner bases public-key cryptography cryptanalysis
Contact author(s): stegers @ cs ucdavis edu
History: 2007-03-16: last of 2 revisions; 2006-11-12: received; See all versions
Short URL: https://ia.cr/2006/404
License: CC BY

BibTeX

@misc{cryptoeprint:2006/404,
      author = {Till Stegers},
      title = {Faugere's F5 Algorithm Revisited},
      howpublished = {Cryptology {ePrint} Archive, Paper 2006/404},
      year = {2006},
      url = {https://eprint.iacr.org/2006/404}
}