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

In the RSA problem one tries to avoid to pick a message $$x \in \mathbb{Z}_N$$. 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 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. – fkraiem Feb 1 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. – Maeher Feb 1 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. ;) – fkraiem Feb 1 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. – fkraiem Feb 1 at 17:09