Geoff Thorpe wrote:
> > > 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.
>
> damn, called my bluff. I'll try and type something in a bit later when I
> have the time. For now though, the basic idea is this: doing a low-prime
> sieve on a candidate "n" is reasonably slow (albeit faster than a
> probabilistic test) ... you take the remainder after dividing n by each
> low prime j and if it's 0, n is not prime. In an arithmetic sequence block
> you can use the low-prime sieve on the first candidate to run across all
> the other candidates very quickly sieving them *without any divisions*.
> Implemented carefully, and with a prudent choice of block sizes, you can
> also get this algorithm optimised to fit inside fast cache memory, and
> also interleave instructions for processor optimisation. I've spec'd this
> out a while ago, and somebody else has since implemented it but I haven't
> seen the stats - but I would expect that a low-prime sieve, even on
> 1000-2000 sequential candidates, to not take much longer than a low-prime
> sieve on just one candidate by itself. After having worked this out, I
> spotted that someone had already done something similar (and slightly
> improved the algorith,) but only in the sequential case ... it was
> documented in "Handbook of Applied Crypto" I think.
>
> Will post more later when I have a chance.
No need (at least, not for me). I understand. Quite neat, but I still
have to believe that it doesn't introduce significant bias.
BTW, it occurs to me that one could extend the sieving idea to
simultaneously sieve (p-1)/2 (or 2p+1) so that safe primes can be
generated more rapidly...
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]
