When polynomial f(x^2) can be factored as g(x)·g(-x) ? In relation to my question Expression for the sum of square roots of zeros of a polynomial
How to characterize polynomials $f(x)$ with rational coefficients such that $f(x^2)=g(x)\cdot g(-x)$ where $g(x)$ is also a polynomial with rational coefficients? 
Is there a computationally efficient way to identify if given polynomial $f(x)$ is such without factoring $f(x^2)$ ?
 A: Letting $g(x) = \sum_0^n a_jx^j$, the coefficient of the $x^{2k}$ term in the product $g(x)g(-x)$ is precisely equal to 
$$
\alpha_k = \sum_{i+j = 2k} (-1)^j a_i a_j
$$
So, if you are given some $f(y) = \sum_{k=0}^n \beta_k y^{k}$, you know that testing whether $f(x^2) = g(x)g(-x)$ reduces to solving the system of multivariate quadratic equations $\alpha_k = \beta_k$ where the $\beta_k$ are specified by your $f$ coefficients and the $\alpha_k$ are as above.
I think no matter which way you cut it, solving a multivariate quadratic system in general is NP hard and unless you get lucky with Buchberger's algorithm, I would not expect an efficient solution.
Update In response to the comment regarding factoring below, yes it is equivalent to testing if $f$ factors. The important thing is: we are testing for factorization rather than computing the factorization. I think the present formulation might offer certain advantages in the case when $f$ does not factor. A certificate of non-existence might be furnished by effective versions of Hilbert's Nullstellensatz.
For instance, if we define the $n+1$ shifted polynomials $$\gamma_k(a_0,\ldots,a_n) = \alpha_k(a_0,\ldots,a_n) - \beta_k,$$ and if there is no set of $a_0,\ldots,a_n$ which simultaneously makes the $\gamma_k$-s vanish, then there must exist polynomials $\delta_k$ so that $$\sum_{k=0}^n \gamma_k\delta_k = 1.$$ More importantly from a computational perspective, the total degree of each $\delta_k$ is bounded by $(n+1)^2 2^{n+1} + 2(n+1)$. For details, see the main theorem of:
Sharp Effective Nullstellensatz. Janos Kollar. Journal of the American Mathematical Society, Vol. 1, No. 4. (Oct., 1988), pp. 963-975
A: (Caveat:  nothing in this response has been checked or even really thought through.)
If it's true with integral coefficients, it's true mod p for all p.  Now the question of whether f(x^2) splits as g(x)g(-x) for f in F_p[x] is the question of whether f is a norm in the quadratic extension obtained by adjoining a square root of x, which should just be a question about whether each irreducible factor p(x) appearing an odd number of times in f splits in that quadratic extension.  By quadratic reciprocity (I think) this comes down to whether each of these irreducible factors p(x) has p(0) a quadratic residue.  This is easy enough to check for lots of p.
Of course, to have any hope, you need f(0) to be a square (as an integer) so I think in practice what I'd do would be to take a long list of primes p, reduce f mod p for each p, and if f factors into p_1(x) ... p_k(x) mod p, check that each p_i(0) is a residue.  And if this keeps on happening you should gain confidence that your f(x^2) actually factors in this way.
