Vincent Hanquez <t...@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 <e...@ertes.de>"
FPrint: BD28 3E3F BE63 BADD 4157 9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/
signature.asc
Description: PGP signature
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
