Re: Faster algorithm for factor?

[Trevor Wilson]

I was wrong in my last reply. Assuming the ERH, we have to check up to
2(ln n)^2 for possible witnesses. This can be up to 3935, but it's not
too much of a slowdown. Up to about 2^48, the least witnesses are known
and are no more than 17, so that saves us some work.

We might also be able to get away with just checking primes as witnesses.
I'm looking into it.

--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 <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?
> 
>