Hi there,
On Sun, 28 Nov 1999, Ben Laurie wrote:
> Geoff Thorpe wrote:
> >
> > 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?
I hope I addressed that in my last post - namely that the k value is
chosen "randomly" at the same time as the starting point. So maybe X has
an unfair chance of discovery when k=1047 because it lies at the end of a
very long gap in its congruence class mod 1047 ... but that doesn't help
it in the slightest if you choose k=1049. And vice versa. If you choose
"large enough" values for k, then even primes lying at the end of
massively long gaps of non-primes are not really biased because skipping
across gaps of size k probably has you leaping past other primes before
landing on top of one. I think this gives you the same sort of probability
spread you'd get by just choosing "random" candidates each time, but as I
said the fact it's an arithmetic sequence gives you the elbow room to do
some major speedups in the low-prime sieving.
> > 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.
Given that the "k" in your arithmetic sequence can be quite high (and my
comment about that above), *and* you can leap about the block of
candidates however you like once you've actually done a low-prime sieve on
it, I don't think you get any "weaknesses" introduced.
> > 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.
Cheers,
Geoff
----------------------------------------------------------------------
Geoff Thorpe Email: [EMAIL PROTECTED]
Cryptographic Software Engineer, C2Net Europe http://www.int.c2.net
----------------------------------------------------------------------
May I just take this opportunity to say that of all the people I have
EVER emailed, you are definitely one of them.
______________________________________________________________________
OpenSSL Project http://www.openssl.org
Development Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
