On efficient computation of grobner bases
Jee Koh, Justin Gash · 2008
On October 2, 2000 the National Institute of Standards and Technology chose to adopt a new cryptographic algorithm as the standard for the United States government. This new system was called Rijndael, named after its creators Vincent Rijmen and Joan Daemon. Though it remains unbroken, cryptanalysts are using so-called Grobner-basis attacks in an attempt to break it. Thus, the onus is now on finding Grobner bases quickly. In 2002 J.C. Faugere published an algorithm called F5 that found Grobner bases dramatically quicker in most cases; however, in some cases, his program failed to terminate. The problem posed is two-fold: (1) Can F5 be improved so that it terminates? (2) Can the hypotheses for termination be tightened? My research has produced a modified F5 algorithm (called F5t) that guarantees termination in all cases. In addition I demonstrate a current accepted major theorem in Grobner basis theory is false. I replace the erroneous theorem by a new theorem, proving that a slightly modified F5 can be made to terminate (correctly) over finite fields.