Elimination ideal and bivariate resultant over finite fields
Gilles Villard · 2023
A new algorithm is presented for computing the largest degree invariant factor of the Sylvester matrix (with respect either to x or y) associated to two polynomials a and b in which have no non-trivial common divisors. The algorithm is randomized of the Monte Carlo type and requires (delog q)1 + o(1) bit operations, where d and e respectively bound the input degrees in x and in y. It follows that the same complexity estimate is valid for computing: a generator of the elimination ideal (or ), as long as the polynomial system a = b = 0 has not roots at infinity; the resultant of a and b when they are sufficiently generic, especially so that the Sylvester matrix has a unique non-trivial invariant factor. Our approach is to use the reduction of the problem to a problem of minimal polynomial in the quotient algebra . By proposing a new method based on structured polynomial matrix division for computing with the elements in the quotient, we manage to improve the best known complexity bounds.