Re: Faster algorithm for factor?

[Jim Meyering]

Trevor Wilson <address@hidden> 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?