> From: Wei Dai <[EMAIL PROTECTED]>
> This code is kind of hard to understand.
More comments about construction. Good idea.....
One of the main reasons for the design was to find as many prime
candidates as possible in one pass, rather than going through all the
work for only one prime, as the various libraries do. Photuris can
select moduli from a frequently changing list, a design feature intended
to discourage anyone from bothering to analyze any particular modulus.
> I couldn't figure out why you're
> using three sieves (large, small, and tiny).
Tiny is for primes from 2 .. 2**16-1.
Small is for primes from 2**16 .. 2**32-2**16. It is derived by
applying the tiny sieve. Saved memory, so that as much memory as
possible could be used for the large sieve.
Large is the large candidate sieve, and is derived by applying the small
sieve.
Experiment found that sieving as much as possible has a significant
reduction of computation effort in the Miller-Rabin. Pushing the small
sieve from 2**24 to 2**32 cut the time for finding 4K-bit primes on my
machine from a week to a weekend.
> Also, your sieve appears to
> sieve candidates for p that are 3 mod 4, but you only need to sieve
> integers that are 11 mod 12.
>
Clever! That would save space in the bit array, at the expense of
additional computation (a shift right 2 being fast compared to mod 12).
Just skipping evens (3 mod 4) was merely more obvious.
> You might want to take a look at the safe prime generation code in
> Crypto++ 3.0 (see the first constructor of PrimeAndGenerator in
> nbtheory.cpp). The sieving code there is influenced by Colin Plumb's
> bignum library.
>
Although not a fan of C++, I will take a look at the recently announced
code. Thanks!
[EMAIL PROTECTED]
Key fingerprint = 17 40 5E 67 15 6F 31 26 DD 0D B9 9B 6A 15 2C 32
