Modified version of Miller-Rabin to test deterministic primality?

Question

The Miller-Rabin test uses k random integers to test for primality.

According to CLRS, 3^rd Edition, Page 971:

Theorem 31.38

If n is an odd composite number, then the number of witnesses to the compositeness of n is at least (n - 1)/2.

Then why don't we just instead of running random tests k times, use different ( n - 1 ) / 2 values and test them for primality? Since all primes except 2 are odd and no of witnesses are atleast ( n - 1 ) / 2 we are guaranteed to find a witness if exists.

Answer 1

The running time goes from poly(log(n)) to n*poly(log(n)), which is terrible for large numbers, since n is exponentially bigger than log(n).