In 2010, Dieulefait and Urroz considered the notion of malleability of an RSA modulus. They proved that, given some information on the factors of numbers coprime to n, where n is an RSA modulus, there exists an algorithm that finds a proper factor of n in time \(O(\log n)\) . As a particular case of their algorithm, just some knowledge of the factors of \(2^n\pm 1\) is enough to factor n except possibly when n is a base-2 pseudoprime. They went on to prove that the set of these exceptional RSA moduli with prime factors between z and 2z has size at most \(O(z^2/(\log z)^3)\) . In the present paper, we improve this bound significantly and show that the counting function for these RSA moduli is bounded above by \(O(z^{8/5}/(\log z)^2)\) . In addition, as a related problem, we prove an upper bound of \(O(z^{4/5}/(\log z)^{2/5})\) for the number of base-2 pseudoprimes up to z that are products of two primes.
