Random comments:

The rational root test might be good for finding all rational roots but less so if one is happy to abort as soon as an irrational root is found (i.e one not of the form $\frac{t}{a_0}$.

If $a_n=1$ then check if $\pm 1$ are roots. If so great! if not then you can factor $a_0$ searching for a factor less than $a_0^{1/n}$. There is some gain from looking further for very small integer divisors, but perhaps not much. If $a_0=1$ then factor $u^nf(1/u)$

This may not be so great if $a_0$ is huge. For example if we replace $f$ by $a_n^{n-1}f(u/a_n)$ to get a monic polynomial with constant term $a_0a_n^{n-1}$

Repeated roots can be tricky for some methods so one might wish to compute $f'$ and find the polynomial gcd since any repeated roots will be roots of that. In your case the gcd of $7x+5$ reveals a double root of $\frac{-5}{7}$ leaving $256x^3+144x^2-826x+51$

Given $f'$, even without bothering with the gcd, one is set to use Newton's method (or some other) to quickly find approximate real roots. Then given a somewhat accurate real root $r,$ one can see if it is close to a rational root. The continued fraction should have a convergent which is remarkably good. Seeing a root near $-0.7$ gives $-.7138457729$ after $5$ iterations. The convergents are $-2/3,-5/7,-227/318, -232/325, -5563/7793$ which gives two reasonable candidates. A couple more iterations would leave no doubt. Your example is not great for illustrating that because the "round off error" quickly gives the exact rational root (as a decimal) if it is of the form $\frac{t}{10^k}$ for $k$ small.

I was excited that Newton's method (although others might be better) returns rationals given rationals, however the denominators grow very quickly. However, the previous observation gives the idea of using Newton's method plus rounding to always get approximants of the form $\frac{t}{a_0}.$ That will quickly get to a root if there is one (I'd think.)

If f is a product of $n$ linear factors the same is true mod $m$ for any $m$. Famously, the converse is not true. However there are algorithms to factor mod $p$ and one failure tells you to stop. I recall methods to lift to factorizations mod $p^k$ but that is back to general integer factorization. Maybe that is easier if you already have linear factors though.

allthe roots will be rational... $\endgroup$ – Joseph O'Rourke May 18 '12 at 13:55