On RSA Moduli with Prescribed Bit Patterns

We give a polynomial time probabilistic algorithm that constructs an RSA modulus M=pl, where p and l are two n-bit primes, which has about n/2 bits, on certain positions, prescribed in advance. Although the number of prescribed bits is less than in other constructions, this algorithm can be rigorously analyzed while the other approaches remain heuristic. The proof is based on bounds of exponential sums. We also show that this algorithm can be used for finding 2n-bit RSA moduli whose binary expansions are of Hamming weight about 3n/4. Finally, similar arguments are also applied to smooth integers.