Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I know that the number 216 + 1 is commonly used for RSA, since 0b 1 0000 0000 0000 0001 only contains two 1 bits. Many sites explain that this makes modular exponentiation faster, but I haven't come across an explanation of why it is faster.

Why is it more efficient to use a number with a lot of zeros for modular exponentiation?

share|improve this question
    
I don't think this is exactly a theoretical question, but I wouldn't mind seeing the answer myself! –  stankewicz Mar 2 '10 at 19:42
    
I don't think "theoretical" per se is a requirement here. –  Scott Morrison Mar 2 '10 at 21:41
    
i think this is a fine question, but i do wish that more questions would use correct capitalization. i find it hard to read uncapitalized posts, and it comes across as unprofessional. –  Theo Johnson-Freyd Mar 2 '10 at 23:46
4  
@Theo, I would encourage you to start downvoting with this as a reason. I'll try to as well! "-1, inability to use <shift> key." –  Scott Morrison Mar 3 '10 at 0:51
5  
@Theo, Scott: why not just edit the post? It's not worth editing for tiny grammatical things, but if it's enough for you to leave a comment or a downvote, I think it's better to just edit. –  Anton Geraschenko Mar 3 '10 at 18:23

2 Answers 2

up vote 4 down vote accepted

There are a two minor advantages to choosing the exponent 216+1.

The first advantage, as Johannes observed, is that for fixed size exponent, exponentiation to power e using the basic repeated squaring method is moderately faster when e has lots of zero bits. It is not true that exponents with more one bits are necessarily slower since there are plenty of such numbers with very short addition chains (though finding such short addition chains is an NP complete problem in general). In any case, e = 3 would be a much better choice than e = 216+1 for the sole purpose of exponentiation.

The second advantage is that 216+1 is a prime number and it is not too small. A requirement of the RSA algorithm is that the exponent e must be relatively prime with φ(pq) = (p-1)(q-1). Since the large primes p and q are chosen randomly, there is always a chance that (p-1)(q-1) is not relatively prime with the (previously chosen) exponent e and the primes p,q must therefore be discarded. So small exponents e are poor choices since about every (e-1)th choice of p and q is a bad one, thus shrinking the overall key space. Choosing e to be a large prime would be best, but too large an e would make exponentiation slow. In the end, e = 216+1 is a nice compromise value.

share|improve this answer
    
I guess a third advantage of 65537 is that it is the smallest exponent allowed by NIST, though they don't give a specific reason for that choice. (Probably to avoid small exponent attacks, which are possible when proper padding is not used.) –  François G. Dorais Mar 3 '10 at 0:03
    
@François G. Dorais: If e=3, couldn't you just avoid generating primes that are 1 mod 3? I assume 0 mod 2 and 3 are being avoided already to save some time. It's not hard to take a random number k and consider 6k+5 as a potential prime. –  aorq Mar 3 '10 at 6:41
    
Yes, that is fine for e=3. It is already difficult for e=5 without further decreasing the key space and/or increasing the key-generation cost. (Note that the real issue with e=3 is the risk of small exponent attacks.) –  François G. Dorais Mar 3 '10 at 14:47
1  
Also, e=3 has the disadvantage that it might be vulnerable to the broadcast attack. If you send a message x using e=3 to 3 different users (with different n_1,n_2,n_3, WLOG, mutually relatively prime (or we'd have a factorisation of 2 of them..) then we could solve x^3 mod n_i (i=1,2,3) using the CRT for x. This is a problem if e=3 were a common exponent. Hence the choice for a relatively large e (also prime and few bits set). –  Henno Brandsma Dec 18 '10 at 10:32

The usually used fast exponentiation algorithm is the so called square-and-multiply-algorithm. It needs exactly n+m multiplications, where n is the total length of the binary written exponent and m is the number of 1-bits in the exponent. Therefore exponentation with 2^16+1 is almost twice as fast as exponentiation with say 2^17-1.

share|improve this answer
    
hi thank you for your answer! can I ask, though, why does it need m+n operations? where is that coming from? thanks again! –  sj steve Mar 2 '10 at 20:54
    
Consider how you might compute something like $5^9$ rapidly. First, compute the numbers $p_0 = 5^{2^0}$, $p_1 = 5^{2^1}$, $p_2 = 5^{2^2}$, and $p_3 = 5^{2^3}$. Each of these is computed from the previous one by squaring, so you have $n-1$ multiplications in total (or $n$ if you start by multiplying 1 by 5 to get $5^{2^0}$). Since 9 is 1001 in binary, you get $5^9$ by multiplying $p_0$ by $p_3$, for $m - 1$ more multiplications (again, $m$ if you start by multiplying 1). In total, we used four multiplications, where you might naively have used nine. –  Matt Noonan Mar 2 '10 at 23:55

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.