# 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 '14 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 '14 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.
• 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 '14 at 16:50