Re: Suggestions for doublehashing scheme
 From: websnarf@xxxxxxxxx
 Date: 11 Jun 2005 01:00:11 0700
Robert Maas, see http://tinyurl.com/uh3t wrote:
> > From: websnarf@xxxxxxxxx
> > I personally don't know how to implement a practical *deterministic*
> > prime number testing algorithm for numbers > 32bits.
>
> Why would you ever need to do that? You're approaching the higherup
> problem backwards, pick a random odd number and then test whether it's
> prime. The better method which I developed for generating large primes,
> way back during the month or two after Ron Rivest published his
> largeprimebased publickeycryptosystem algorithm in Scientific
> American, was to directly synthesize the number p1 (within a desired
> range) as an explicit product of primes with appropriate statistics,
> and then with that known factorization of p1 you can easily prove
> whether p is prime or not.
You don't say ... well, if this actually delivered a polynomial time
algorithm, I'd be impressed (since the existence of such a thing, as
far as I know, was only established a few years ago). Of course, if
you had something that was practical only up to, say, 64 bits, that
would be good too (at least for about 50 years, it will be) but
certainly it is using ideas I am not aware of.
Which is really my whole point. If the algorithm is over my head, then
chances are, that there is a fairly small audience who will be able to
understand it. So, who's going to be able to audit the code?
Sometimes, you just need large prime numbers, and good probabilistic
techniques are well known, but building something where you and
everyone interested is sure of its correctness and runs in practical
execution time is just one of those kind of hard problems.

Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
.
 FollowUps:
 Re: Suggestions for doublehashing scheme
 From: Robert Maas, see http://tinyurl.com/uh3t
 Re: Suggestions for doublehashing scheme
 From: Tim Rentsch
 Re: Suggestions for doublehashing scheme
 References:
 Re: Suggestions for doublehashing scheme
 From: Robert Maas, see http://tinyurl.com/uh3t
 Re: Suggestions for doublehashing scheme
 Prev by Date: Re: beginner's attempt at hash function
 Next by Date: Re: alphabetizing in BASIC
 Previous by thread: Re: Suggestions for doublehashing scheme
 Next by thread: Re: Suggestions for doublehashing scheme
 Index(es):
Relevant Pages
