Welcome to MathOverflow

Question

2

I know that the number 2¹⁶ + 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?

edited Mar 3 2010 at 18:26

Anton Geraschenko♦♦
13.7k●3●48●108

asked Mar 2 2010 at 19:37

sj steve
39●2

I don't think this is exactly a theoretical question, but I wouldn't mind seeing the answer myself! – stankewicz Mar 2 2010 at 19:42

I don't think "theoretical" per se is a requirement here. – Scott Morrison♦ Mar 2 2010 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 2010 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 2010 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 2010 at 18:23

François G. Dorais · Accepted Answer · 2010-03-03 14:30:14Z UTC

There are a two minor advantages to choosing the exponent 2¹⁶+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 = 2¹⁶+1 for the sole purpose of exponentiation.

The second advantage is that 2¹⁶+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 = 2¹⁶+1 is a nice compromise value.

Johannes Hahn · Answer 2 · 2010-03-02 19:44:56Z UTC

6

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.

answered Mar 2 2010 at 19:44

Johannes Hahn
1,725●6●12

	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 2010 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 2010 at 23:55

modular exponentation for RSA, why is 2^16 + 1 commonly chosen?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.