Resultant

The resultant of two polynomials is a value computed from their coefficients that equals zero exactly when the two polynomials share a common root, possibly in an extension of the field. It is a foundational tool of computer algebra, applied to eliminate a variable when solving systems of polynomial equations, to perform cylindrical algebraic decomposition, to integrate rational functions, and to determine whether curves defined by polynomials intersect. Because a naive determinant-based computation from the Sylvester matrix costs on the order of the cube of the polynomial degree, computer algebra systems instead favor faster approaches: a Euclidean-algorithm-style computation using polynomial remainder sequences, subresultant sequences that avoid fractions and greatest-common-divisor computation on coefficients, or computing the resultant modulo many prime numbers and reconstructing the exact value with the Chinese remainder theorem. The fastest known methods reduce the problem to fast integer and polynomial multiplication, with cost proportional to that multiplication cost times the logarithm of the input size.