Re: Suggestions for double-hashing scheme

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/

.

Relevant Pages

  • Re: Suggestions for double-hashing scheme
    ... if this actually delivered a polynomial time ... If the algorithm is over my head, ... The code runs much faster testing even numbers for primality. ... From: Robert Maas, see http://tinyurl.com/uh3t ...
    (comp.programming)
  • Re: Suggestions for double-hashing scheme
    ... Robert Maas, see http://tinyurl.com/uh3t wrote: ... >> If the algorithm is over my head, then chances are, that there is a ... not sure what guarantees your algorithm provides, ... difficult algorithm to feed a "halting problem determiner" (it has the ...
    (comp.programming)