Is it necessary, that the public key is a prime number in the RSA algorithm?

Question

I read some books talk about RSA cryptography but I did not understand something when choosing a public key $e$ Sometimes the condition is

$1<e<$$\phi(n)$

Where $\phi(n) = p-1 * q-1$

also sometimes is

$e \in [{1,2,...,\phi(n)-1}]$

also sometimes is

$e$ should be prime number

Examble

Choose $p = 3\ and\ q = 11 $

Compute $n = p * q = 3 * 11 = 33 $ Compute $\phi(n) = (p - 1) * (q - 1) = 2 * 10 = 20$
Choose $e$ .here can choose e = 7 where 7 is prime number or I can choose $e=9$ where 9 is relatively prime to 20.

My question

Are both states right when choose 7 and 9. or not right .If no why???

Answer 1

There is no specific reason why $e$ is required to be a prime number. It must be relatively prime to $\phi(n)$ (otherwise we can't decrypt uniquely); however that is the only hard requirement. Assuming that 9 is relatively prime to $\phi(n)$, there is no reason why 9 can't be used as a public exponent.

However, selecting a prime value for $e$ does have this practical advantage; for prime $e$, then the requirement that it is relatively prime to $\phi(n)$ is equivalent to the statements that $p \ne 1 \pmod{e}$ and $q \ne 1 \pmod{e}$ (where $p$ and $q$ are the prime factors of $n$). If we use the common logic of selecting $e$ first, and then $p$ and $q$, this turns into a relatively simple additional criteria when doing prime selection.

Answer 2

Working with small primes for P and Q is difficult to provide good examples.

Normally primes have an advantage, as Poncho points out. However, in your case, when e=7 then d=3. When e=9 then d=9. Thereby not a good example where it would normally be fine.