6
$\begingroup$

The short exponents in RSA which are only a few bits in length,i.e. $e=3,\ 17$ and $2^{16} +1$

Why we are using exponents of the form ${}2^n+1$ not $2^n-1$?

$\endgroup$
  • $\begingroup$ There is no actual rule about it but it would be nice if you would accept answers if they sufficiently answer your question. You can hit accept by hitting the V mark next to the answer. If there is anything missing, don't hesitate to ask for clarification (but don't ask a separate question in the comments). $\endgroup$ – Maarten Bodewes Dec 12 '16 at 23:03
10
$\begingroup$

The keys of form $2^n + 1$ only contain two bits set (the ones in your question are also short prime values, in case you didn't notice). The public exponents of form $2^n - 1$ on the other hand contain a lot of bits set when $n$ grows (the value 3 is obviously both 10 + 1 in binary as well as 100 - 1 in binary).

Modular exponentiation is usually deemed more efficient if only a few bits are set. At least it is easier to see how to implement it efficiently. The public exponent is usually a prime to make it easier to find a value of $p$ where the public exponent is relative prime to $p - 1$.

Note that $2^{16}+1= 1\ 0000\ 0000\ 0000\ 0001b$ and $2^{16}-1=1111\ 1111\ 1111\ 1111b$. So there is quite a difference in the number of bits set (2 against 16). As the value is 65535 in decimal, it is quite obviously not a prime either as it divides by 5. Then again, $2^{17} - 1 = 1\ 1111\ 1111\ 1111\ 1111b$ is prime and contains as many bits.

The primes with just 2 bits set (the first and last one) are called Fermat primes. There are currently five known Fermat primes: $$F_0 = 2^{1} + 1 = 3$$ $$F_1 = 2^{2} + 1 = 5$$ $$F_2 = 2^{4} + 1 = 17$$ $$F_3 = 2^{8} + 1 = 257$$ $$F_4 = 2^{16} + 1 = 65537$$ if there are any others (this is an open math problem) they will most definitely not be small primes.


For comparison, try to calculate both $6\times999$ and $6\times1001$ in normal decimals. It is easy to see why this calculation is efficient.

[EDIT] I did do some performance measurements on Java 8 build 71 and I did not find a (consistent) difference between Fermat and Mersenne primes. This could be due to the information that Poncho provided:

Note: $e=2^{16}+1$ can be computed with 16 squarings and 1 multiplication; $e=2^{16}−1$ can be computed with 15 squarings and 4 multiplications; calling the former 'much more efficient' appears to be a bit of an exaggeration...

But it could also be due to side channel protection in the Java runtime. In the end it will depend on the implementation as well. It does seem to show a common misconception that Fermat primes should always be (much) faster than other primes. I would not be surprised if Fermat primes are just more entrenched than other values.


The following are the known Mersenne primes (values that are both prime and of form $2^{n}-1$) up to $2^{31}-1$.

$$2^{3}-1 = 7$$ $$2^{5}-1 = 31$$ $$2^{7}-1 = 127$$ $$2^{13}-1 = 8191$$ $$2^{17}-1 = 131071$$ $$2^{19}-1 = 524287$$ $$2^{31}-1 = 2147483647$$

I'll be surprised if I see a use for these Mersenne primes as public exponent within RSA though.

| improve this answer | |
$\endgroup$
  • $\begingroup$ In fact, Mersenne primes of the form $2^n-1$ seem quite a bit more common than Fermat primes, of which we currently know only five examples (3, 5, 17, 257 and 65537). But, as you correctly note, they're also much less useful as RSA exponents. $\endgroup$ – Ilmari Karonen Nov 20 '16 at 23:12
  • $\begingroup$ @IlmariKaronen Thanks for the tip about Mersenne primes. Afterwards you always remember you already know about these kind of things :) $\endgroup$ – Maarten Bodewes Nov 20 '16 at 23:45
  • 2
    $\begingroup$ Note: $e = 2^{16}+1$ can be computed with 16 squarings and 1 multiplication; $e = 2^{16}-1$ can be computed with 15 squarings and 4 multiplications; calling the former 'much more efficient' appears to be a bit of an exaggeration... $\endgroup$ – poncho Nov 21 '16 at 14:50
  • $\begingroup$ @poncho right you are. Actually, it seems that although this seems to be the main reason for using a Fermat prime instead of a Mersenne prime, i did not see any noticable difference on my Java platform. Then again, thats also implementation specific, e.g. I don't know if there are side channel protection measures used even though public key is used; it could use the same modular exponentiation as for privete key ops without CRT. $\endgroup$ – Maarten Bodewes Nov 21 '16 at 14:58
  • $\begingroup$ I suspect the real reason Fermat primes are used is mostly because of convention; it's obvious how to minimize the multiplications (while the 19 operation I listed for $2^{16}-1$ might not occur to a naive implementor); and given there's no other reason, well, that's what people pick. As for side channel attacks, well, the value $e$ is public, and so it's not like we need to hide the squaring/multiplication order... $\endgroup$ – poncho Nov 21 '16 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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