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
