Vincent Hanquez
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