Weak Keys in RSA with Primes Sharing Least Significant Bits

Let N = pq be an LSBS-RSA modulus where primes p and q have the same bit-length and share the m least significant bits, and (p - 1, q - 1) = 2. Given (N, e) with e ∈ Z*Φ(N)/4 that satisfies ew + z ċ 22(m-1) = 0 (mod Φ(N)/4) with 0 < w ≤ 1/9√Φ(N)/e N1/4+θ and |z| ≤ c ew/Φ(N) N1/4-θ, we can find p and q in polynomial time. We show that the number of these weak keys e is at least N3/4+θ-e, where θ = m/log2 N, and there exists a probabilistic algorithm that can factor N in time O(N1/4-θ+e).