Miller-Rabin primality test can be made deterministic when the number $n$ is small, for example "if $n < 2047$, it is enough to test [with base] $a = 2$".
How are those bases found? By brute force? Say I pick an upper bound 2047 and test many different bases to see if any of them always returns correct primality outcomes?
On
No base will always return the correct result. The chance that base b doesn't recognise a random composite number c as prime is less than 1/4, probably less than 1/8. So you can just go and find composite numbers that are not found with base = 2, then amongst those the composite numbers that are not found with base = 3, and the more bases you use, the fewer exceptions you will have. Even a rough estimate says that fewer than one in a billion numbers will pass the test for the first ten primes. You can just write some software that finds the first pseudo-prime for any set of bases.
If you want a bit better results, you could create a sieve of pseudo-primes for the first 20 primes, then you can quickly check which set of 10 gets you furthest, and then you can check larger bases to see which ones will catch the few counterexamples that you have.
Or you can do some research and find better methods to find sets with few counterexamples.
You do it the other way round. You give a set of bases that are tested and look which composites pass the test based on this set.
In particular interesting is the smallest composite number passing the test.
If the set is, for example {$2,3$}, the smallest counterexample is $$1373653$$ Hence we can say : If $n<1373653$ and $n$ is a strong Fermat-pseudoprime to bases $2$ and $3$ , then $n$ is prime.
The poulet-numbers are calculated upto a large limit, using these numbers we can (assuming that the set contains $2$) accelerate the search dramatically, but since the poulet-numbers were basically found by brute force, there is probably no better method to find the smallest counterexamples (or good base-combinations with a large smallest counter-example) than brute force.