F4 ALGORITHM WITH THE F5'S CRITERIA
Celia Tonelli · Dialnet (Universidad de la Rioja) · 2012
Faugere in [2] gave an algorithm called F4 to compute more e ciently G- bases of ideals (of K[x1, . . . , xn]) based on linear algebra, therefore inspired by Lazard (1983). Later in [3] Faugere published the algorithm F5 which has two strong criteria to detect S-polynomials whose reduction is zero, without explicitly calculating the re- duction. However it took some years [4] to give a proof that F5 is correct ( it returs a G-basis whenever it stops) and, as far as we know, it is only known that F5 stops under some modi cations [1]. However F4 with FGLM, and F5 algorithms have been sucesfully applied to solve overdetermined systems of equations coming from public cryptography (as HFE), and symmetric cryptography (streem cipher and block ciphers). In our ex- position we explain these algorithms, according with Faugere recommendation [3] ...to translate F5 in F4fashion and show examples coming from HFElike systems. References [1] C. Eder, J. Gash, J. Perry, Modifying Faugeres's F5 Algorithm to ensure termination.. arXiv: 1006.0318, (Dec. 2010). [2] J.C. Faugere, A new e cient algorithm for computing Grobner bases (F4) (1999), Journal of Pure and Applied Algebra 139, no. 1-3, pp.61-88. [3] J.C. Faugere, A new e cient algorithm for computing Grobner bases without reduction to zero (F5) (2002), ISSAC '02: Proceedings of the 2002 international symposium on Symbolic and algebraic com- putation (New York, NY, USA), ACM Press, pp. 75-83. [4] J.M.Gash, On e cient computation of Grobner bases (2008), Ph.D. Thesis, University of Indiana. [5] D. Lazard, Grobner-bases, gaussian elimination and resolution of systems of algebraic equations (1983), EUROCAL (J. A. van Hulzen, ed.), Lecture Notes in Computer Science, vol. 162, Springer, pp. 146-156. Universita di Pisa, Universidad Complutense de Madrid E-mail address: [email protected]