<div dir="ltr"><div class="gmail_extra">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.</div><div class="gmail_extra"><br></div><div class="gmail_extra">I am not saying OpenSSL should or should not do this check, but hopefully making that decision is easier knowing the runtime penalty.</div><div class="gmail_extra"><br></div><div class="gmail_extra">Bill</div></div>