Geoff Thorpe wrote:
>
> Hi there,
>
> On Sun, 28 Nov 1999, Ben Laurie wrote:
>
> > Geoff Thorpe wrote:
> > >
> > > I can't recall whether the prime number generation uses sequential
> > > candidates or an arithmetic sequence (or even something else) but I don't
> > > think that would qualify as a "known problem" either way ...
> >
> > Sequential candidates or an arithmetic sequence would both effectively
> > reduce the randomness of the primes, because they'd both favour primes
> > that come after long gaps.
>
> sequential yes, arithmetic not *really*. :-)
No?
> The basic idea is to give each prime (in some region of the integers) a
> roughly equal shot at being hit by the prime number search. Sequential
> searches do not do that - eg the second prime in a prime pair (where two
> sequential odd numbers are both prime) has an extremely low chance of
> being stumbled across in a sequential search because the search would have
> to begin right on top of it. An arithmetic search increases the "fair
> play" by skipping across intervals plucking candidates out every 'k' odd
> numbers. Provided no ground-breaking maths crops up and you choose good
> 'k's, I think it pretty much evens the playing field.
You mean you think there aren't primes commonly separated by k except
when k=2?
> However, even with sequential searches - the real problem is not entropy
> as someone has shown (I can't recall who, Peter Gutmann showed me a paper
> ages back about this - perhaps he can recall - Peter, you there?). There
> is a slight reduction in the effective key-space from an entropy point of
> view but bounds were given on the loss of entropy due to the bias towards
> some primes over others. The scary thing about sequential searches is that
> nobody seems to know whether or not heavily favouring primes following
> long gaps happens to heavily favour primes with particular numerical or
> algebraic properties that may undermine the security of those keys (or
> facilitate a much faster factor search that gives preferences to such
> primes).
Interesting point.
> > What OpenSSL does is choose a fresh random number each time. Umm. I
> > think (I checked the code a while ago, but not recently).
>
> I don't think this is such a hot idea - for a start you gobble up your
> available entropy like crazy zooming about over vast numbers of
> candidates, most of which aren't prime. I'd say it was better to use up
> good entropy by ("carefully"?) choosing a starting point for the prime
> search rather than using it all up on lots of candidates that get thrown
> away almost immediately. There are other ways to get round "candidate
> bias" after you've got that starting point than purely using up the
> entropy pool.
You don't have to consume any more entropy this way, you are just
following a much less predictable sequence - that is, you put all your
entropy into your PRNG at step 1, then away you go.
> Also, this makes doing low-prime sieves a lot slower as you have to
> process them one at a time. When doing sequential (or arithmetic) searches
> you can perform low-prime sieves in a large block *much* faster than doing
> them individually (I can elaborate if you like) ... as most candidates
> sneaking past a low-prime sieve go on to be real primes (using
> probabilistic tests) it makes low-prime sieving a major performance
> consideration.
Another interesting point, but should I accept the aforementioned
weaknesses in order to get this performance gain? I suspect not.
> As a side note (again, I'll elaborate if anyone gives a hoot) there are
> some cool ways to avoid (or lessen) candidate bias whether using
> sequential or arithmetic sequences that still allow you to do fast
> low-prime sieves on large blocks rather than one at a time.
Please do.
Cheers,
Ben.
--
http://www.apache-ssl.org/ben.html
"My grandfather once told me that there are two kinds of people: those
who work and those who take the credit. He told me to try to be in the
first group; there was less competition there."
- Indira Gandhi
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
