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: There is no finite set of bases working for every number. 
But the SPRP-test is much faster than ECPP. Using random bases, the probability can be made so small, that there is no doubt that the checked number is prime.
If the extended riemann-hypothesis is true, then a SPRP-test upto
$2\cdot ln(n)^2$ guarantees that the checked number is prime.
If your number does not have more than $500$ digits, the APR-test (Adleman-Pomerance-Rumely-test) is deterministic and the computational complexity is nearly polynomial. You should get a fast result with a powerful tool.
PARI/GP is not very fast, but it only takes about $2,5$ minutes for a $500$-digit number using APR.
If your number is greater than this threash-hold, I would suggest the SPRP-test (You can take the first primes , lets say , upto $100$ and additionally , lets say , $20$ random bases). 
Even in the worst-case-scenario (which occurs extremely rare) , a composite number passes a SPRP-test using $k$ distinct random bases with probability $(\frac{1}{4})^k$. So, for $k=100$, you get a probability of less than $10^{-60}$. This is absolutely sufficient for practical purposes (for example cryptography).
It has been proven, that primilaty checking is in $P$ , but I  do not know a concrete program doing this.
Primo is probably the most powerful primality proving program, but I have no clue which algorithm is used.
A: 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}$.
