Why are Fermat primes ($2^{2^n}+1$) useful as $e$ (the public key) in RSA encryption?

I understand why $2^n+1$ primes are useful, because they would simply be 100...001 in binary, which for computers is faster in calculations. But why is it important that the exponent is also a power of 2?

  • $\begingroup$ Hint: what is a necessary condition for $2^n+1$ to be prime? $\endgroup$
    – fgrieu
    Jan 29, 2014 at 16:26
  • $\begingroup$ One part of the question is not addressed yet: why would one want $e$ prime in RSA? Hint: consider how hard it is to meet the requirement $\gcd(e,p-1)=1$ for $e=2^4+1$ and $e=2^5+1$. $\endgroup$
    – fgrieu
    Jan 30, 2014 at 7:39

1 Answer 1


All primes of the form $2^n+1$ have the form $2^{2^n}+1$.

As the wikipedia article on Fermat numbers says:

If $2^n + 1$ is prime, and $n > 0$, it can be shown that $n$ must be a power of two. (If n = ab where $1 ≤ a$, $b ≤ n$ and $b$ is odd, then $2^n + 1 = (2^a)^b + 1 ≡ (−1)^b + 1 = 0 \pmod{2^a + 1}$. See Sec. 5 for complete proof.) In other words, every prime of the form $2^n + 1$ is a Fermat number, and such primes are called Fermat primes.

The only known numbers with this format are 3, 5, 17, 257 and 65537.

  • $\begingroup$ Addition: Pierre de Fermat wrongly believed/conjectured that $\forall n\in\mathbb N,2^{2^n}+1$ is prime; when he could have disproved that reasonably easily for $n=5$ using his own little theorem, and the modern belief is that it is unlikely to hold for any $n>4$. $\endgroup$
    – fgrieu
    Jan 29, 2014 at 16:50
  • $\begingroup$ I'm not sure they are these are the only Fermat numbers. According to Wikipedia there are others. Are the ones you mentioned the ones commonly used with RSA? $\endgroup$
    – rath
    Jan 29, 2014 at 17:07
  • 2
    $\begingroup$ @rath We're talking about primes with this format. There are infinitely many Fermat numbers, but only these few are prime $\endgroup$ Jan 29, 2014 at 17:12
  • $\begingroup$ Okay, now I feel stupid. I thought Fermat numbers were of the above format and prime. $\endgroup$
    – rath
    Jan 29, 2014 at 17:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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