In general you can't write $p = f^2 + g^2$ in ${\bf Q}[x]$ at all, let alone do so efficiently.

For example, $2 x^2 + 3$ is positive for all $x$ (and is the sum of three squares, $(x+1)^2 + (x-1)^2 + 1^2$); but if $2 x^2 + 3 = f(x)^2 + g(x)^2$ then $3 = f(0)^2 + g(0)^2$, which is impossible because $3$ is not a sum of two rational squares. (Cf. the comment of Olivier Bégassat.)

A positive quadratic polynomial can still be written as $a f(x)^2 + b g(x)^2$ for rational $a,b > 0$; but in degree $4$ and beyond even that is not usually true, for Galois-theoretic reasons, using the factorization $a f^2 + b g^2 = a (f+cg) (f-cg)$ with $c^2 = -b/a$. For example, if $p$ has degree $n$ and Galois group $S_n$ (which is the usual case) then $p$ cannot be written as $a f^2 + b g^2$. Already $p = x^4 + x + 1$ is an example.

In general you can't write $p = f^2 + g^2$ in ${\bf Q}[x]$ at all, let alone do so efficiently.

For example, $2 x^2 + 3$ is positive for all $x$ (and is the sum of three squares, $(x+1)^2 + (x-1)^2 + 1^2$); but if $2 x^2 + 3 = f(x)^2 + g(x)^2$ then $3 = f(0)^2 + g(0)^2$, which is impossible because $3$ is not a sum of two rational squares. (Cf. the comment of Olivier Bégassat.)

A positive quadratic polynomial can still be written as $a f(x)^2 + b g(x)^2$ for rational $a,b > 0$; but in degree $4$ and beyond even that is not usually true, for Galois-theoretic reasons, using the factorization $a f^2 + b g^2 = a (f+cg) (f-cg)$ with $c^2 = -b/a$. For example, if $p$ has degree $n$ and Galois group $S_n$ (which is the usual case) then $p$ cannot be written as $a f^2 + b g^2$. Already $p = x^4 + x + 1$ is an example.

In general you can't write $p = f^2 + g^2$ in ${\bf Q}[x]$ at all, let alone do so efficiently.

For example, $2 x^2 + 3$ is positive for all $x$ (and is the sum of three squares, $(x+1)^2 + (x-1)^2 + 1^2$); but if $2 x^2 + 3 = f(x)^2 + g(x)^2$ then $3 = f(0)^2 + g(0)^2$, which is impossible because $3$ is not a sum of two rational squares. (Cf. the comment of Olivier Bégassat.)

A positive quadratic polynomial can still be written as $a f(x)^2 + b g(x)^2$ for rational $a,b > 0$; but in degree $4$ and beyond even that is not usually true, for Galois-theoretic reasons, using the factorization $a f^2 + b g^2 = a (f+cg) (f-cg)$ with $c^2 = -b/a$. For example, if $f$ has degree $n$ and Galois group $S_n$ (which is the usual case) then $f$ cannot be written as $a f^2 + b g^2$. Already $f = x^4 + x + 1$ is an example.

In general you can't write $p = f^2 + g^2$ in ${\bf Q}[x]$ at all, let alone do so efficiently.

For example, $2 x^2 + 3$ is positive for all $x$ (and is the sum of three squares, $(x+1)^2 + (x-1)^2 + 1^2$); but if $2 x^2 + 3 = f(x)^2 + g(x)^2$ then $3 = f(0)^2 + g(0)^2$, which is impossible because $3$ is not a sum of two rational squares. (Cf. the comment of Olivier Bégassat.)

A positive quadratic polynomial can still be written as $a f(x)^2 + b g(x)^2$ for rational $a,b > 0$; but in degree $4$ and beyond even that is not usually true, for Galois-theoretic reasons, using the factorization $a f^2 + b g^2 = a (f+cg) (f-cg)$ with $c^2 = -b/a$. For example, if $p$ has degree $n$ and Galois group $S_n$ (which is the usual case) then $p$ cannot be written as $a f^2 + b g^2$. Already $p = x^4 + x + 1$ is an example.