> Is that what we want maxima to do? Declare something is
> prime if it is probably prime by passing the Rabin-Miller test?
First of all, a quick glance at Andrei's code seems to show that it is
using the non-probabistic case of Rabin-Miller, which gives primality
*proof* for n < 10^14+. So there is no problem there.
Secondly, I do agree as a general principle that Maxima should give
correct answers, not probably correct answers. This is important
because Maxima is not applied to random cases, but to cases that the
user finds interesting, for example pseudoprimes, or the independence of
random number generators when applied to primality testing.
That said, Rabin-Miller is too good to ignore; Maxima is not a purist
system, but a pragmatic one; and there is a non-zero probability of
other kinds of calculation error (cosmic ray hits CPU, maybe 1 in
10^-16?). So I would suggest that in cases where Rabin-Miller is not
definitive, we give a warning message if it determines the number to be
prime:
Warning: Probabilistic test determined XXX to be prime: false positive
with probability 10^-XXX.
We could get more elaborate than that (e.g. turning probabilistic
on/off, making the number of test bases parameterizable, having a switch
for primality algorithm, giving progress reports for very long
calculations, etc.), but I would first want to hear from people who
really care about these things, e.g. number theorists and
cryptographers. My experience as a product manager shows that users'
needs are usually not the same as what we imagine they are.
-s