Subresultant Polynomial Remainder Sequences Obtained by Polynomial Divisions in Q[x] or in Z[x]

Abstract

In this paper we present two new methods for computing the
subresultant polynomial remainder sequence (prs) of two polynomials f, g ∈ Z[x].
We are now able to also correctly compute the Euclidean and modified
Euclidean prs of f, g by using either of the functions employed by our
methods to compute the remainder polynomials.

Another innovation is that we are able to obtain subresultant prs’s in
Z[x] by employing the function rem(f, g, x) to compute the remainder
polynomials in [x]. This is achieved by our method subresultants_amv_q
(f, g, x), which is somewhat slow due to the inherent higher cost of com-
putations in the field of rationals.

To improve in speed, our second method, subresultants_amv(f, g,
x), computes the remainder polynomials in the ring Z[x] by employing the
function rem_z(f, g, x); the time complexity and performance of this
method are very competitive.

Our methods are two different implementations of Theorem 1 (Section 3),
which establishes a one-to-one correspondence between the Euclidean and
modified Euclidean prs of f, g, on one hand, and the subresultant prs of f, g,
on the other.

By contrast, if – as is currently the practice – the remainder polynomi-
als are obtained by the pseudo-remainders function prem(f, g, x) 3 , then
only subresultant prs’s are correctly computed. Euclidean and modified Eu-
clidean prs’s generated by this function may cause confusion with the signs
and conflict with Theorem 1.

ACM Computing Classification System (1998): F.2.1, G.1.5, I.1.2.