On RSA moduli with almost half of the bits prescribed (Q1003703): Difference between revisions

For an integer \(n \geq 1\), let \(M_n\) denote the set of RSA moduli \(m=pl\) that are products of two distinct primes \(p\) and \(l\) such that \(2^{n-1} < p, l < 2^n\). The authors show that using character sum estimates due \textit{H. Iwaniec} [Invent. Math. 23, 97--104 (1974; Zbl 0275.10024)] leads to an improvement of recent results about the distribution and finding RSA moduli \(m \in M_n\) with prescribed bit patterns. More exactly, it is shown that the algorithm previously proposed by the second author [Des. Codes Cryptography 39, No. 1, 113--122 (2006; Zbl 1172.11047)] allows to specify in expected polynomial time about \(n\) bits instead of about \(n/2\) bits as in the above paper of I. Shparlinski. Also some other arithmetic and combinatorial applications of the same result of H. Iwaniec are demonstrated.