That's a good question. It has been proven that 3/4 of numbers are witnesses for any given composite, so using 8 would give 1/2^16 chance of error. However, in practice this seems to be much better. Unfortunately, the greatest least witness (not a typo) for all numbers up to 2^64 has not yet been calculated.
If we are willing to assume the Extended Riemann Hypothesis, which has not yet been proven, but no one really doubts, then it suffices to check for witnesses up to 2 ln ln 2^64 < 8. However, I should use 2,3,4,5,6,7,8 rather than choosing randomly. --Trevor "Mathematics is like checkers in being suitable for the young, not too difficult, amusing, and without peril to the state." --Plato On Mon, 5 Jan 2004, Jim Meyering wrote: > Trevor Wilson <[EMAIL PROTECTED]> wrote: > > Yes, there is a bug for inputs >= 2^63 where the program does not > > necessarily terminate. The program uses the Rabin-Miller primality test, > > so it should return on primes almost immediately in general. > > Oh, yes. I see you already mentioned that. > > Here's perhaps a more fundamental question: > Can we really use a probabilistic algorithm here? > > > #define RMTRIALS 8 > > So if `factor' outputs a factor, that factor is truly prime with > probability 1 - 2^-8. That doesn't seem to be close enough to 1.0. > > Has it been shown that using just 8 witnesses is sufficient to guarantee > accurate primality testing for all numbers smaller than 2^64? > In any case, this would seem to depend on the implementation and seeding > of `rand' (or some other pseudo-random number generator), so can we get > any guarantee, in general? > > _______________________________________________ Bug-coreutils mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/bug-coreutils
