# Re: Suggestions for double-hashing 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 higher-up

> 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

> large-prime-based public-key-cryptosystem algorithm in Scientific

> American, was to directly synthesize the number p-1 (within a desired

> range) as an explicit product of primes with appropriate statistics,

> and then with that known factorization of p-1 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/

.

**Follow-Ups**:**Re: Suggestions for double-hashing scheme***From:*Robert Maas, see http://tinyurl.com/uh3t

**Re: Suggestions for double-hashing scheme***From:*Tim Rentsch

**References**:**Re: Suggestions for double-hashing scheme***From:*Robert Maas, see http://tinyurl.com/uh3t

- Prev by Date:
**Re: beginner's attempt at hash function** - Next by Date:
**Re: alphabetizing in BASIC** - Previous by thread:
**Re: Suggestions for double-hashing scheme** - Next by thread:
**Re: Suggestions for double-hashing scheme** - Index(es):