Gr?bner Bases Computation and Mutant Polynomials.

      Аннотация: Gr?bner bases are the single most important tool in applicable algebraic geometry. This is in part because they can be used to solve systems of polynomial equations. Applications in science and technology are abundant, particularly in cryptography and coding theory. Gr?bner bases computation is challenging and a great deal of effort has been devoted to improve algorithms to compute faster larger bases. The concept of mutant polynomials, introduced by Ding in 2006, characterizes a phenomenon of degeneration in the process of Gr?bner bases computation. Exploiting the appearance of mutant polynomials has led to significant improvements in Gr?bner bases Computation. In this work we describe several such improvements and we establish some theoretical results for mutant polynomials. We also propose LASyz, a method to avoid redundant computation in Gr?bner bases computation that is compatible with mutant algorithms. This is achieved by simple linear algebra procedures used to compute generators for the module of syzygies. Overall, this book provides an introduction to the state-of-the-art in Gr?bner bases computation together with the first steps towards a theory of mutant polynomials.

Ключевые слова: Groebner Bases, Syzygies, Cryptanalysis, Mutant Polynomials