Mills Test Running Time Can Miller's Test be replaced with the bound below in hopes that it would make a faster general-purpose primality test (compared to ECPP). 
If $n$ is an $a$-SPRP for all primes $a$ $<$ ($\log_2 n$)/$2$, then $n$ is prime.
I checked the bounds for the first few prime bases $a$, and the tests are deterministic for:
If $n$ $<$ $2^4$ is a $2$-SPRP, then $n$ is prime.
If $n$ $<$ $2^6$ is a $2, 3$-SPRP, then $n$ is prime.
If $n$ $<$ $2^{10}$ is a $2, 3, 5$-SPRP, then $n$ is prime.
If $n$ $<$ $2^{14}$ is a $2, 3, 5, 7$-SPRP, then $n$ is prime.
$.........$
I did this up to $2^{74}$ to test prime bases $2$ to $37$ and all results are deterministic, but I am running short on a proof.
$1.$ Can anyone find a counterexample or show the bound above is accurate.
$2.$ If the running time of the test above is faster than ECPP?

A lot of work has been done on the Miller-Rabin primality test to examine how large a number can be (deterministically) assessed with a few given bases, see wikipedia chapter here. According to that, testing with the prime bases up to $37$ is good to $ 318665857834031151167461 \approx 2^{78}$.
