most recent 30 from http://mathoverflow.net 2013-05-20T07:10:09Z http://mathoverflow.net/feeds/question/16901 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/16901/modular-exponentation-for-rsa-why-is-216-1-commonly-chosen sj steve 2010-03-02T19:37:23Z 2010-03-03T18:26:36Z

<p>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.</p> <p>Why is it more efficient to use a number with a lot of zeros for modular exponentiation?</p>

http://mathoverflow.net/questions/16901/modular-exponentation-for-rsa-why-is-216-1-commonly-chosen/16904#16904 Johannes Hahn 2010-03-02T19:44:56Z 2010-03-02T19:44:56Z

<p>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.</p>

http://mathoverflow.net/questions/16901/modular-exponentation-for-rsa-why-is-216-1-commonly-chosen/16935#16935 François G. Dorais 2010-03-02T23:27:12Z 2010-03-03T14:30:14Z

<p>There are a two minor advantages to choosing the exponent 2¹⁶+1. </p> <p>The first advantage, as Johannes observed, is that for fixed size exponent, exponentiation to power e using the <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring" rel="nofollow">basic repeated squaring method</a> 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 <a href="http://en.wikipedia.org/wiki/Addition-chain_exponentiation" rel="nofollow">addition chains</a> (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.</p> <p>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 &phi;(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.</p>