Signature Based Strategies for Gröbner Bases Computation

In this thesis we give an insight into the behaviour of signature-based algorithms for computing a Gröbner basis for a given ideal, summarizing the last decade of research in this field. Since 1965 when Buchberger first gave a definition of Gröbner bases this topic has been extensively studied for its high number of application, but computations may require a lot of effort time and storage space, and so many strategies to improve this process have been investigated. A first possible improvement is implemented in the F4 algorithm which uses linear algebra to massively parallelize the reduction process. In what follows we focus on the so called signature strategies, which consist in enriching the structure from ideal to free finitely generated module and using the information contained in the latter to avoid useless computations. In fact we can associate to every polynomial a module element that is its signature let algorithms operate on these labeled polynomial in order to correctly update signature and to obtain new criteria to predict in advance reductions to zero. In 2002 the French mathematician J.C. Faugere announced the breaking of the Hidden Field Equations (HFE) challenge, a well known cryptographic system, in 96 hour using a new algorithm to compute the Gröbner basis of a polynomial system. This last algorithm, known as the F5 algorithm, gave astonishing experimental results, and it is one of the main topic of this work. After analyzing the two criteria implemented and commenting the pseudo code we discuss the proof of correctness and termination, the latter being formulated only by Galkin in 2012. The termination of the F5 is a key point, since until 2012 it was not clear how the new criteria could lead to finite loops, and that is the reason why many authors developed slightly modified versions of this algorithm ensuring termination. At this purpose we describe many of these variants, such as F5B, F5t, F5+, F5C, F5R and F4/5 which combines the use of signatures with an F4-stylish reduction. In the last chapter we make generalization of the theories analyzed in the particular case of the F5, leading to the definitions of signature Gröbner basis and rewriting basis. For the sake of completeness we conclude by describing G2V and GVW, two algorithms which are not directly derived from Faugère's work, but an interesting example of how this general setting affects computations.