[Haskell-cafe] ANN: crypto-pubkey: all your public key crypto algorithms belong to us.

[Ertugrul Söylemez]

Vincent Hanquez <tab at 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 at ertes.de>"
FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/haskell-cafe/attachments/20130114/31441cf8/attachment.pgp>