# Usage of Fermat primes in RSA

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?

• Hint: what is a necessary condition for $2^n+1$ to be prime?
– fgrieu
Jan 29, 2014 at 16:26
• 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$.
– fgrieu
Jan 30, 2014 at 7:39

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

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.

• 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$.
– fgrieu
Jan 29, 2014 at 16:50
• 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?
– rath
Jan 29, 2014 at 17:07
• @rath We're talking about primes with this format. There are infinitely many Fermat numbers, but only these few are prime Jan 29, 2014 at 17:12
• Okay, now I feel stupid. I thought Fermat numbers were of the above format and prime.
– rath
Jan 29, 2014 at 17:19