[Steven]
> ... Try it on numbers like this:
> ...
> Q = P*(313*(P-1)+1)*(353*(P-1)+1)
>
> Q is a 397 digit Carmichael Number. Its smallest factor is P,
> which has 131 digits.
> ...
> My old and slow PC can prove that Q is a composite number,
> using pure Python, in less than six seconds.
>
> And I'm sure that a better programmer than me would be
> able to shave off some of that time.

The pure-Python Miller-Rabin code i posted in the aforementioned thread is typically at least 100 times faster than that.  But it's not deterministic.  Because it tries (pseudo)random bases, it all depends on how many it needs to try on each run before finding a witness to that Q is composite.  It usually (at least 75% of runs) finds one on the first try.

BTW, it doesn't much matter that this is "pure Python" - for ints of this size the bulk of the time regardless is spent in CPython's C-coded bigint arithmetic.  I expect that your code must be doing more than _just_ Miller-Rabin, and in the Q case is paying through the nose for "optimizations" that all fail before getting to Miller-Rabin.

About the API, I can't agree to the one you propose.  Different applications have different appropriate tradeoffs between degree of certainty and time consumed - "one size fits all" doesn't fly here.

    def probably_prime(n, maxsteps=20)

supplies a _default_ instead.  I don't want an API that's useful _only_ to people who don't know what they're doing ;-)
 

> (By the way: for smallish numbers, under 2**64, no more than
> twelve rounds of Miller-Rabin are sufficient to
> deterministically decide whether a number is prime or not.

But only if you use a fixed set of 12 specific bases for which the claim has been proved.  "Real" Miller-Rabin picks bases at random, relying only on properties that have been proved independent of the argument size.

[Vedran]
> Tim: Considering that congruence is _defined_ as
> x=y(mod m) :<=> m|y-x, it's
> really not so surprising. :-)

Didn't say it was ;-)  Was just noting the odd coincidence that I just happened to stumble into a real use for lcm(), not previously mentioned in this report, while doing something else.