[pycrypto] getStrongPrime() implementation

[Lorenz Quack]

Hi,

as promised here is the implementation of a getStrongPrime() function which generates strong primes as described in
the paper [1].
Let me know if such a thing is of interest and if so what could be improved.
Really any comments are welcome.
I didn't benchmark or use this in any meaningful way, yet.
But it is expected to be quite a bit slower than the implementation used so far for at least two reasons:
  1) the base for the sieve is much larger (here 10000 in contrast to 54)
  2) a lot more calls to mpz_probab_prime_p (Rabin-Miller-Tests) are used (75 per strong prime vs 5)
I chose those numbers in accordance with the paper [1] but there is probably room for a security/performance trade-off.


yours,

Lorenz

________________________________________________________________________________________________

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.2713&rep=rep1&type=pdf
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: getStrongPrime.patch
Url: http://lists.dlitz.net/pipermail/pycrypto/attachments/20091021/5de74650/attachment-0001.txt