I know that the public exponent is always a prime, but what about the private exponent? Is it always a prime too?

  • 4
    $\begingroup$ The public exponent doesn't have to be a prime. $\endgroup$ – Thomas May 14 '14 at 23:54
  • $\begingroup$ The exponent has to be coprime to the totient $\phi(n)$. And then the private exponent will also be coprime to $\phi(n)$. $\endgroup$ – tylo May 15 '14 at 14:30

Actually, the public exponent doesn't have to be prime; any odd number works just fine there. The most common public exponents (3, 17, 65537) all happen to be prime, but there's no requirement.

Now, it turns out that a prime public exponent does make RSA key generation slightly easier in this respect; when you select primes $p$ and $q$, we need to make sure that $p-1$ and $q-1$ are both relatively prime to the public exponent $e$. If the public exponent $e$ happens to be prime, then this is equivalent to saying that $p \ne 1 \pmod e$ and $q \ne 1 \pmod e$; these can be easy tests to fold into the prime search. If $e$ is composite, then the conditions are slightly more complex -- certainly not impossible to accomplish, to be sure.

That said, the private exponent need not be a prime number. All the private exponent $d$ is is a number such that $de \equiv 1 \pmod{ \operatorname{lcm}(p-1, q-1) }$; $d$ will always be odd, but there's no specific reason why it can't be (say) a multiple of 3.

  • 1
    $\begingroup$ Specifically, $d$ is going to be an integer such that $ed - 1 = k\cdot \mathrm{lcm}(p - 1, q - 1)$ for some integer $k$, that is, $d = \frac{k \cdot \mathrm{lcm}(p - 1, q - 1) + 1}{e}$, so, really, its prime factorization could be anything, except it will always be coprime to $\mathrm{lcm}(p - 1, q - 1)$, that's about all you can say. $\endgroup$ – Thomas May 15 '14 at 22:30
  • 1
    $\begingroup$ @Thomas: indeed, you expressed it better than I did $\endgroup$ – poncho May 16 '14 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.