Elimination ideal and bivariate resultant over finite fields
share
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 𝔽_q[x,y] which have no non-trivial common divisors. The algorithm is randomized of the Monte Carlo type and requires O((de)^1+ϵlog(q) ^1+o(1)) bit operations, where d an 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 ⟨ a,b ⟩∩𝔽_q[x] (or 𝔽_q[y]), as soon 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 𝔽_q[x,y]/⟨ a,b ⟩. 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.
READ FULL TEXT