Y.-D. Zhao and W.-F. Qi “Small Private-Exponent Attack on RSA with Primes Sharing Bits.” (ISC 2007) ISC 2007 - Programに発表資料があるので見てた. N=pqとして, pまたはqの半分のビットが既知の場合 d<N^{0.292}の場合 のいずれかで, LLLを用いてdを知ることが出来るというのは良く知られている話. B. de Wegerが2002年に, pとqの差が小さい場合にはdの制限が緩くても良いということを話したらしい *1. この場合, pとqの上の方のビットを共有していると言える. では, 「逆は?」という発想の下, pとqの下の方のビットが同じという仮定から色々話をしている. nをセキュリティパラメータとして, p, qをn/2ビットの素数とする. 下の(1/2