Skip to main content
3 of 3
added 173 characters in body
user avatar
user avatar

$\varphi(n)$ is a multiplicative function: it is computed by the formula

$$ \varphi(n) = n \prod_{p \mid n} \frac{p-1}{p} $$

or something equivalent. This is basically the only method of computation known that remains feasible when $n$ is not small.

Thus, if $N$ is the modulus you want to use for RSA, you need to know its prime factorization so that you can compute $\varphi(N)$. And you don't want anyone else to know it's prime factorization, otherwise they could compute $\varphi(N)$.

Also, all RSA cares about is that it has some $N$ and $\varphi(N)$. The only reason we talk about $p$ and $q$ is because choosing $N=pq$ because it is the best way to satisfy the previous paragraph.

user25578