[openssl-dev] common factors in (p-1) and (q-1)

[Bill Cox]

Cool observation.  From running a bit of Python code, it looks like the
probability that GCD(p-1, p-q) == 4 is a bit higher than 15%, at least for
random numbers between 2048 and 4096 bits long.  It looks like putting in a
GCD(p-1, q-1) check will slow down finding suitable p and q by around a
factor of 6.5.

I am not saying OpenSSL should or should not do this check, but hopefully
making that decision is easier knowing the runtime penalty.

Bill
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mta.openssl.org/pipermail/openssl-dev/attachments/20150731/376f0636/attachment.html>