I'd have to hear back from Raymond more on what he had in mind - I may well have been reading far too much in the specific name he suggested.

Don't much care about API, etc - pick something reasonable and go with it.  I'm not overly ;-) concerned with being "newbie friendly".  If someone is in a context where they need to use probabilistic solutions, there is no substitute for them learning something non-trivial about them.  The usual API for a Miller-Rabin tester supports passing in the number of bases to try, and it's as clear as anything of this kind _can_ be then that the probability of getting back True when the argument is actually composite is no higher than 1 over 4 to the power of the number of bases tried.  Which is also the way they'll find it explained in every reference.  It's doing nobody a real favor to make up our own explanations for a novel UI ;-)

BTW, purely by coincidence, I faced a small puzzle today, as part of a larger problem:

Given that 25 is congruent to 55 mod 10, and also mod 15, what's the largest modulus we can be certain of that the congruence still holds?  IOW, given

    x = y (mod A), and
    x = y (mod B)

what's the largest C such that we can be certain

    x = y (mod C)

too?  And the answer is C = lcm(A, B) (which is 30 in the example).