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

## DOI:

https://doi.org/10.55630/sjc.2016.10.197-217## Keywords:

Euclidean algorithm, Euclidean polynomial remainder sequence (prs), modified Euclidean (Sturm’s) prs, subresultant prs, modified subresultant prs, Sylvester matrices, Bezout matrix, Van Vleck’s method, sympy## Abstract

In this paper we present two new methods for computing thesubresultant 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.