Gröbner Bases Computation and Mutant Polynomials
Daniel Cabarcas · OhioLink ETD Center (Ohio Library and Information Network) · 2013
Gröbner bases are the single most important tool in applicable algebraic geometry.They are used to compute standard representatives in the residue classes of a polynomial ring modulo an ideal and they can be used as a step towards solving a system of polynomial equations.Applications in science and technology are abundant, particularly in cryptography and coding theory.Computation of Gröbner bases is challenging.It has computational complexity double exponential in the worst-case and exponential in average.Although this makes Gröbner bases intractable in many cases, a great deal of effort has been devoted to improve algorithms to compute faster larger Gröbner bases.The concept of mutant polynomials, introduced by Ding in 2006, quantifies the deviation from the average case, leading to faster algorithms that profit on this degeneration.In this dissertation we introduce three algorithms aiming at improving Gröbner bases computation that are inspired by mutant polynomials.The MutantF 4 algorithm modifies Faugère's F 4 by exploiting the presence of mutant polynomials.The MXL3 algorithm introduces a termination condition based on the absence of mutant polynomials.And the MGB algorithm combines MXL3 with the idea of preempted reduction to avoid storing large sets of polynomials.Each new idea