Re: Suggestions for double-hashing scheme

Robert Maas, see 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