It is hard to factor an RSA modulus in the most simple sense: given a number n which is a product of two primes n=pq (slightly big, say), then, in general, we do not know how to find p and q. In 2006, P. Paillier and J. Villar conjectured that this problem would still be hard even if we knew how to factor integers m coprime to n (they do this with the help of a certain oracle).

Even though the conjecture seems completely reasonable, it is subtle how to formulate it. In this talk we will build, for any modulus n, certain explicit m coprime to n which will indeed allow us to factor n knowing only very partial information about the factorization of m itself.

This is joint work with L. Dieulefait .