  Assessing non-negativity of multivariate polynomials over the reals, through
the computation of {\em certificates of non-negativity}, is a topical issue in
polynomial optimization. This is usually tackled through the computation of
{\em sums-of-squares decompositions} which rely on efficient numerical solvers
for semi-definite programming. This method faces two difficulties. The first
one is that the certificates obtained this way are {\em approximate} and then
non-exact. The second one is due to the fact that not all non-negative
polynomials are sums-of-squares. In this paper, we build on previous works by
Parrilo, Nie, Demmel and Sturmfels who introduced certificates of
non-negativity modulo {\em gradient ideals}. We prove that, actually, such
certificates can be obtained {\em exactly}, over the rationals if the
polynomial under consideration has rational coefficients and we provide {\em
exact} algorithms to compute them. We analyze the bit complexity of these
algorithms and deduce bit size bounds of such certificates.
