  Pourchet proved in 1971 that every nonnegative univariate polynomial with
rational coefficients is a sum of five or fewer squares. Nonetheless, there are
no known algorithms for constructing such a decomposition. The sole purpose of
the present paper is to present a set of algorithms that decompose a given
nonnegative polynomial into a sum of six (five under some unproven conjecture
or when allowing weights) squares of polynomials. Moreover, we prove that the
binary complexity can be expressed polynomially in terms of classical
operations of computer algebra and algorithmic number theory.
