Let be two bivariate polynomials over an effective field , and let be the reduced Gröbner basis of the ideal generated by and with respect to the usual degree lexicographic order. Assuming and sufficiently generic, we design a quasi-optimal algorithm for the reduction of modulo , where “quasi-optimal” is meant in terms of the size of the input . Immediate applications are an ideal membership test and a multiplication algorithm for the quotient algebra , both in quasi-linear time. Moreover, we show that itself can be computed in quasi-linear time with respect to the output size.

Authors: Joris van der Hoeven, Robin Larrieu

Keywords: Gröbner basis, polynomial reduction, algorithm, complexity

View: Html, TeXmacs, Pdf, BibTeX