Research On F5-like Algorithms

The F5algorithm and its improved algorithms such as SAGBI-F5, F5C, EF5, G2V andGVW are collectively called F5-like algorithms. F5-like algorithms are universally supposed tobe the most efficient algorithms for Gr bner bases computation and a standard tool of algebraicattacks on cryptographic systems. At present, F5-like algorithms are a key part of research ofGr bner bases computation and also a hot and difficult subject of cryptanalysis. In this thesis, wesystematically study F5-like algorithms from theories of strong Gr bner bases, generalizedcriteria, algorithm models, proofs of termination, and reduction algorithms. Specifically, themain contributions in this thesis are as follows:1. A model for criteria of F5-like algorithms. In this paper, we present the main content ofthe theory of strong Gr bner bases based on the existing theories of F5-like algorithms. Then ageneralized model for the criteria of F5-like algorithms is proposed by introducing some newconcepts such as L-pair and criterion order. It has been proved that the model can specialize toall existing criteria of F5-like algorithms when specializing the criterion order to appropriatespecific orders. It means that the criteria of F5-like algorithms can be proved or designed byfinding the corresponding criterion order or designing new criterion orders respectively based onthe criterion model. Compared with Sun’s GBGC model, our model proves that all F5-likealgorithms can use the criteria for L-pair and compute not only Gr bner bases but also strongGr bner bases.2. Generalized models of F5-Like algorithms. The definition of F5-like algorithms, themodel of non-incremental F5-like algorithms, the model of incremental F5-like algorithms, themodel of F5-like algorithms for computing Gr bner bases in quotient rings, and an example ofF5-like algorithms, are given respectively based on the criterion model. The sub-algorithms andthe structure of F5-like algorithms are systematically discussed by introducing some newconcepts such as selection order, regular reduction algorithm and lexicographical module order.It is proved that a selection strategy of J-pairs or S-pairs is equivalent to a selection order, andthat the reduction algorithms of F5-like algorithms should be regular. Moreover, a model ofcriteria of incremental F5-like algorithms is proposed by using the concept of lexicographicalmodule order.3. The termination of F5-Like algorithms. By introducing some new concepts such as ghostsequences and eventually regular reduction algorithms, we prove that the F5-like algorithmsusing almost compatible orders and eventually regular reduction algorithms can terminate for allinputs. It means that the problem of proving the termination of F5-like algorithms such as EF5, GVW, TRB, F5GEN and so on is solved. It is also proved that the termination of F5-Likealgorithms has nothing to do with the selection strategy of J-pairs or S-pairs but that thereduction algorithms are one of the most decisive factors of the termination of F5-like algorithms.Besides, we study the termination of F5-like algorithms with not almost compatible orders andpoint out a class of cases which was ignored in Huang’s proof of the termination of TRB.4. Accelerating F5-Like algorithms by improving reduction algorithms. By analyzing threespecial methods of the F5reduction algorithm named redundant reduction algorithm, criterionreduction algorithm and ghost reduction algorithm respectively combing with experiment results,an improved F5division algorithm is proposed which accelerates F5and F5C effectively. Thenwe present an improved GVW criterion and its corresponding reduction algorithm. Comparedwith the G2V reduction algorithm, they can avoid regular reductions after exiting super reduction,and not need to store and use the coefficients of signature of polynomial, which greatly improvethe efficiency of G2V and GVW. A new division algorithm named head-term-division algorithmis proposed which only reduces the head term of the dividend. Experiment results indicate thatthe incremental F5-like algorithms using the head-term-division algorithm including F5, F5Cand G2V are at least two times faster than the original incremental F5-like algorithms. What’smore, the larger the polynomial system is, the more obvious the effect is.