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.

Dr. Cabarcas is a passionate researcher and a devoted professor of algebraic computation and cryptography. After obtaining his Ph.D. in Mathematics from the University of Cincinnati, he worked at the prestigious Center for Advanced Security Research Darmstadt. He then became professor at the National University of Colombia, Medellín.