Going up to n is surely excessive. You need a version of the Riemann hypothesis to get any sort of logarithmic bound, but a sqrt(n) bound can be achieved using

Going up to n is surely excessive. You need a version of the Riemann hypothesis to get any sort of logarithmic bound, but a sqrt(n) bound can be achieved using unconditional Polya-Vinogradov type inequalities. (A successful Miller-Rabin test corresponds to a nontrivial value of a Dirichlet character, and Polya-Vinogradov ensures that the least such value cannot exceed sqrt(n) * ln(n), unconditionally without the need for any Riemann hypothesis.) A reference for this material is "Explicit bounds for primality testing and related problems" by Eric Bach, Math. Comp. 55 (191), July 1990, pp. 355-380.