分野別セミナー

In this talk, I will describe miniGB, a Buchberger-style Gröbner-basis solver that we have developed for solving the "CS" challenge, a nickname that we've given to the task of solving the multivariate polynomial equations from Gaudry-Diem's ECDLP attack. The main difference between miniGB and previous Buchberger-style solvers such as F4 is that it keeps a "minimal" basis of the ideal throughout the whole computation process. This makes miniGB run faster and use less memory when solving "mutant-rich" systems such as those arising from Weil descent in Gaudry-Diem's ECDLP attack. Incidentally, we discovered that this is precisely how the "F4 algorithm" is implemented in MAGMA 2.21, the best F4 implementation publicly known and widely used in various system-solving experiments. I will also describe other design trade-offs in miniGB and present our preliminary experiment results toward solving the "CS" challenge.