Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
The public exponent doesn't have to be a prime. – Thomas May 14 '14 at 23:54
The exponent has to be coprime to the totient $\phi(n)$. And then the private exponent will also be coprime to $\phi(n)$. – tylo May 15 '14 at 14:30
up vote 5 down vote accepted

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.

share|improve this answer
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. – Thomas May 15 '14 at 22:30
@Thomas: indeed, you expressed it better than I did – poncho May 16 '14 at 0:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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