Vincent Hanquez <tab@snarc.org> wrote:
Also for the particular purpose of generating safe primes I have written a blazingly fast implementation that uses intelligent sieving and finds even large primes (>= 4096 bits) within seconds or minutes. It's on hpaste [2]. I might turn this into a library at some point.
Seconds or minutes ? that's very different :-) But in any case, it would be a nice addition i think.
My safe prime generation function is probably the most naive possible.
Ok, let me give you an actual number. I want, for an integer b > 3, the smallest integer d such that 2^b - d is a safe prime. Let's find all safe primes for b <- [100..399]: % time ./primes {100..399} 2^100 - 12389 2^101 - 9009 ... 2^398 - 128981 2^399 - 191301 ** timings: real 32.355 user 32.105 krnl 0.113 cpu% 99% But of course I have four cores, and as a Haskell programmer I feel that I should use them: % time ./primes {100..399} +RTS -N 2^100 - 12389 2^101 - 9009 ... 2^398 - 128981 2^399 - 191301 ** timings: real 11.047 user 38.194 krnl 3.833 cpu% 380% At some point I'm going to parallelize even individual prime searches. =) Greets, Ertugrul -- Key-ID: E5DD8D11 "Ertugrul Soeylemez <es@ertes.de>" FPrint: BD28 3E3F BE63 BADD 4157 9134 D56A 37FA E5DD 8D11 Keysrv: hkp://subkeys.pgp.net/