[ Homepage | Publications | Talks | TeXmacs |
Mathemagix ] |

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:**

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