Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
    
Hint: what is a necessary condition for $2^n+1$ to be prime? –  fgrieu Jan 29 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 at 7:39
add comment

1 Answer

up vote 3 down vote accepted

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.

share|improve this answer
    
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 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 at 17:07
2  
@rath We're talking about primes with this format. There are infinitely many Fermat numbers, but only these few are prime –  CodesInChaos Jan 29 at 17:12
    
Okay, now I feel stupid. I thought Fermat numbers were of the above format and prime. –  rath Jan 29 at 17:19
add comment

Your Answer

 
discard

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.