[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Faster algorithm for factor?
From: |
Jim Meyering |
Subject: |
Re: Faster algorithm for factor? |
Date: |
Mon, 05 Jan 2004 18:36:27 +0100 |
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?
Re: Faster algorithm for factor?, Trevor Wilson, 2004/01/05