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 '14 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 '14 at 7:39

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.

| improve this answer | |
  • $\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 '14 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 '14 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$ – CodesInChaos Jan 29 '14 at 17:12
  • $\begingroup$ Okay, now I feel stupid. I thought Fermat numbers were of the above format and prime. $\endgroup$ – rath Jan 29 '14 at 17:19

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.