# In RSA, what is $P[x \notin \mathbb{Z}_N^*]$

In the RSA problem, picking a message $$x \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*$$ implies factorizing $$N$$. Since factorization with respect to the standard RSA generator is hard assuming the RSA problem is hard, it is likely that selecting $$x \in \mathbb{Z}_N \setminus \mathbb{Z}_N^*$$ is hard. Thus, one may ask the question:

Given $$x$$ uniformly distributed over $$\mathbb{Z}_N$$ what is the probability that $$x \notin \mathbb{Z}_N^*?$$

with the hope that it is negligible. So I write:

$$P[x \notin \mathbb{Z}_N^*] = 1 - \frac{\phi(N)}{N} = \frac{1}{p}+\frac{1}{q} - \frac{1}{pq}$$

However, how does one prove this is negligible?

• Hint: $p$ and $q$ both are large, including much larger than $4^k$ for $k$-bit security. Note: since you hypothesized that $N=p\,q$ with primes $p$ and $q$ such that $\phi(N)=(p-1)(q-1)$, you must have $p\ne q$; and then it is no longer necessary to restrict to $\Bbb Z_N^*$ for RSA; see Does RSA work for any message $m$.
– fgrieu
Feb 1 '19 at 16:32
• "one tries to avoid to pick a message $x \in \mathbb Z_N$" Whatever you meant to say here, it's probably wrong. Feb 1 '19 at 16:45
• @fkraiem Probably $x\in \mathbb{Z}_N\setminus \mathbb{Z}_N^*$. Though, yes you do not try to avoid it, you just need that it doesn't happen except with negligible probability. Feb 1 '19 at 16:56
• @Maeher Well, clearly if you can produce such an $x$, you can factor $N$, so it should go without saying that it is infeasible. ;) Feb 1 '19 at 17:02
• Basically, "one tries to avoid" makes it sound like "you could do it if you wanted to, but it's better not to", while in fact you just can't. Feb 1 '19 at 17:09

If we consider the generator working on a security parameter of $$n$$ bits (meaning resistance to $$\mathcal O(2^n)$$ computational effort), then each of the prime $$p$$ and $$q$$ must be at least (about) $$n$$-bit, otherwise trial division would factor the public modulus. Then, $$N=p\,q$$ with $$p$$ and $$q$$ distinct primes at least $$2^n$$ implies $$P[x \notin \mathbb{Z}_N^*]=1-\frac{(p-1)(q-1)}{p\,q}<\frac1p+\frac1q<\frac2{2^n}$$, that is $$\mathcal O(2^{-n})$$ which is negligible.