= Solution
The essential exponent condition is
$$
\gcd\bigl(3,(p-1)(q-1)\bigr)=1.
$$
Otherwise the <modular multiplicative inverse> defining $d$ does not exist. For large <prime numbers> greater than three, this is equivalent to
$$
\boxed{p\equiv q\equiv2\pmod3.}
$$
If, for example, $p\equiv1\pmod3$, the multiplicative group modulo $p$ has order divisible by three, and cubing is not a <bijection>; distinct <plaintexts> can have the same <ciphertext>. Unique <decryption> of all messages would then be impossible.
The <prime numbers> must also be distinct for the displayed totient formula, and selected sufficiently large and independently that <integer factorization> of $n=pq$ is infeasible. A small factor, equal factors, or an exceptionally small difference between $p$ and $q$ gives an avoidable factorisation weakness. These size and generation conditions address security; the congruence condition addresses invertibility of cubing.
Back to article page
