It seems to me that the obvious algorithm via the rational root theorem is somewhat inefficient in at least two cases: $a_0$ or $a_n$ is BIG (so that we might not even be able to factor it), or they have A LOT of prime factors.
Instead, I believe the following algorithm based on Hensel's lifting lemma is more suited here.
Let $\displaystyle F = \sum_{i=0}^n a_i X^i \in \mathbb{Z}[X]$ be our polynomial, which we may assume to have no multiple root. Now pick a prime $p$ which does not divide $a_n$ and pass to $\mathbb{Z}/p \mathbb{Z}.$ If $F$ has no root over $\mathbb{Z}/p \mathbb{Z}$ (this requires $p$ checks), then $F$ has no rational root. (The fact we assumed $F$ has no multiple root over the integers does not necessarily mean it still has no multiple root over $\mathbb{Z}/p\mathbb{Z},$ but this can easily be circumvented by a suitable choice of $p.$) Otherwise, use Hensel's lemma to lift the roots $r_k$ from $\mathbb{Z}/p^k \mathbb{Z}$ to $\mathbb{Z}/p^{2k} \mathbb{Z},$ where $k$ is to be chosen later. (this works fine since $p \nmid F'(r_k)$) Finally, we need to get back to the integers, from a root $r_k \in \mathbb{Z}/p^k \mathbb{Z}$ (where we may choose $k$). To an element from $\mathbb{Z}/p^k\mathbb{Z}$, we associate the unique integer from its congruence class mod $p$ which is between $-p^k/2$ and $p^k/2.$ If we choose $k$ so large that $p^k$ is greater than $2 |a_n a_0|,$ then $a_nX - a_n/ba$ (which is a factor of $F$ if $bX-a \in \mathbb{Z}[X]$ is) remains unchanged by the above association, but $a_nX - a_n/ba = a_n(X - r_k)$ in $(\mathbb{Z}/p^k \mathbb{Z})[X]$ and $a_n(X - r_k) = a_nX - \rho$ where $\rho$ is obtained by the above association. We are done now: divide $a_nX - \rho$ (which is an integer multiple of $bX - a$) by $\gcd(a_n, \rho)$ and check the divisibility of $F$ by this reduced factor.
