Counting RSA-integers (Q941100): Difference between revisions

The aim of this paper is to establish an asymptotic formula for the number of integers \(n\leq x\) such that \(n\) is the product of two primes of comparable size; these integers have an important role in the RSA cryptosystem. Let \(C_r(x)\) denote the number of \(n= pq\leq x\) with \(p\), \(q\) primes satisfying \(p< q< rp\). Using the prime number theorem and elementary arguments the authors prove that as \(x\to\infty\) \[ C_r(x)={2x\log r\over\log^2x}+ O\Biggl({r\log(er)x\over \log^3 x}\Biggr), \] and they point out that this is a non-trivial result if \(r= o(\log^3x/\log\log x)\). The acknowledgments explain that Beene de Weger posed the problem to the second author; he gave it to a group of interns at the Max-Planck-Institut für Mathematik in Bonn including the first author who essentially solved it.