4
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ I don't think this is exactly a theoretical question, but I wouldn't mind seeing the answer myself! $\endgroup$
    – stankewicz
    Mar 2, 2010 at 19:42
  • 1
    $\begingroup$ I don't think "theoretical" per se is a requirement here. $\endgroup$ Mar 2, 2010 at 21:41
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 2, 2010 at 23:46
  • 4
    $\begingroup$ @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." $\endgroup$ Mar 3, 2010 at 0:51
  • 5
    $\begingroup$ @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. $\endgroup$ Mar 3, 2010 at 18:23

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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.) $\endgroup$ Mar 3, 2010 at 0:03
  • $\begingroup$ @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. $\endgroup$
    – aorq
    Mar 3, 2010 at 6:41
  • $\begingroup$ 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.) $\endgroup$ Mar 3, 2010 at 14:47
  • 3
    $\begingroup$ 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). $\endgroup$ Dec 18, 2010 at 10:32
  • $\begingroup$ For why security authorities recommend $e=2^{16}+1$ rather than $e=3$, see this. $\endgroup$
    – fgrieu
    Mar 25, 2018 at 8:54
8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ hi thank you for your answer! can I ask, though, why does it need m+n operations? where is that coming from? thanks again! $\endgroup$
    – sj steve
    Mar 2, 2010 at 20:54
  • $\begingroup$ 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. $\endgroup$ Mar 2, 2010 at 23:55
0
$\begingroup$

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

This didn't seem to be answered directly. Optimal addition chain lengths and construction (for say integer $n$) are known when $v(n)$ is small. $v(n)$ is the Hamming weight (number of 1 bits in the binary representation). The length of the smallest addition chain for $n$ is denoted $l(n)$. Simple bounds prove the following addition chain to be optimal: $1,2,4,...,2^{16},2^{16}+1$. If $l(n)=d$ then $n \leq 2^d$ since you can at most double for each step. So $l(2^{16}+1) \geq 17$. The construction of the chain above completes the proof that $l(2^{16}+1)=17$. Now in general the larger $v(n)$ the more non-doubling steps you need in a chain. Doubling does not increase the number of 1's in a number but general multiplies do. Non-doubling steps can at most double the number of ones. We expect that $l(n) \geq \lfloor log_2(n) \rfloor+log_2(v(n))$ but it remains unproven except for small $v(n)$ values and computer searches for $n \leq 2^{64}$ We spit chain steps into two types. With a chain of $1=a_0,a_1,...,a_d=n$ if $\lfloor log_2(a_i) \rfloor= \lfloor log_2(a_{i+1}) \rfloor$ we say step $i$ is a small step. Otherwise it's a large or big step. Calculating optimal addition chains is all about reducing the small steps. We feel that the small step count ($s(n)=l(n)-\lfloor log_2(n) \rfloor$) is a measure of the complexity of $n$. Non-doubling steps eventually add to the small step count since $s(n) \geq f/3.271$ (see Knuth vol 2 4.6.3 Theorem A) with $f$ as the number of non-doubling steps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.