The correct statement is given by the deterministic Miller-Rabin test coupled with an estimate of Bach under GRH.

**Theorem.** Assume GRH. Let $n$ be an odd integer, and write $n-1$ as $2^st$ with $t$ odd. Then $n$ is composite if and only if there is $1<b<2\log^2 n$ coprime with $n$ such that
$b^t\not\equiv 1\pmod{n}$ and $b^{2^r t}\not\equiv -1\pmod{n}$ for some $0\leq r<s$.

For more details see Section V.1 in Koblitz: A course in number theory and cryptography (2nd edition, GTM 114, Springer, 1994).