cryptographynt.number-theoryprime numbers
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?
Suppose you have a diophantine problem whose solution is connected with the structure of the p-class group of a number field K. Then you have the following options:
Experience with descent on elliptic curves has shown me that ultimately, the equations you have to solve in methods 1 and 2 are the same; moreover, the approach using ideals is a lot less technical than using factorial domains in S-integers (the class group relations come back in through the larger rank of the group of S-units). I am certain that the route via the Hilbert class field is even more technical: again, the unit group in the class field will produce more difficulties than a trivial class group will eliminate.
Edit. As an example illustrating my point in a very simple example, let me solve the diophantine equation $x^2 + 5y^2 = z^2$ in several different ways. I will always assume that $\gcd(x,y) = 1$.
1. Elementary Number Theory
The basic idea is factoring: from $5y^2 = (z+x)(z-x)$. Since $d = \gcd(z-x,z+x) = \gcd(2z,z+x) \mid 2$ we have $d = 1$ or $d = 2$; moreover we clearly have $z-x > 0$. This gives $z+x = da^2$, $z-x = 5db^2$ or $z+x = 5da^2$, $z-x = db^2$. Solving for $x$ and $z$ yields $$ x = \pm \frac d2 (a^2 - 5b^2), \quad y = dab. $$
2. Parametrization
Set $X = \frac xz$ and $Y = \frac yz$; then $X^2 + 5Y^2 = 1$. Take the line $Y = t(X+1)$ through the obvious point $(-1,0)$; the second point of intersection is given by $$ X = \frac{1-5t^2}{1+5t^2}, \quad Y = \frac{2t}{1+5t^2}. $$ Dehomogenizing using $t = \frac ba$ and $X = \frac xz$ etc. gives the projective parametrization $$ (x:y:z) = (a^2-5b^2:2ab:a^2+5b^2). $$ If $ab$ is odd, all coordinates are even, and we find $$ x = \frac12(a^2 - 5b^2), \quad y = ab; $$ if $a$ or $b$ is even we get $$ x = a^2 - 5b^2, \quad y = 2ab $$ as above.
3. Algebraic Number Theory
Consider the factorization $$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$ in the ring of integers of the number field $K = {\mathbb Q}(\sqrt{-5}\,)$. The class number of $K$ is $2$, and the ideal class is generated by the prime ideal ${\mathfrak p} = (2,1+\sqrt{-5}\,)$.
The ideal $(x + y\sqrt{-5}, x - y\sqrt{-5}\,)$ is either $(1)$ or ${\mathfrak p}$; thus $$ (x + y\sqrt{-5}\,) = {\mathfrak a}^2, \quad (x - y\sqrt{-5}\,) = {\mathfrak b}^2 $$ in the first and $$ (x + y\sqrt{-5}\,) = {\mathfrak p}{\mathfrak a}^2, \quad (x - y\sqrt{-5}\,) = {\mathfrak p}{\mathfrak b}^2 $$ in the second case.
The second case is impossible since the left hand side as well as ${\mathfrak a}^2$ are principal, but ${\mathfrak p}$ is not. We could have seen this immediately since $x$ and $y$ cannot both be odd.
In the first case, assume first that ${\mathfrak a} = (a + b\sqrt{-5}\,)$ is principal. Since the only units in ${\mathcal O}_K$ are $\pm 1$, this gives $x + y \sqrt{-5} = \pm(a+b\sqrt{-5}\,)^2$ and hence $$ x = \pm (a^2 - 5b^2), \quad y = \pm 2ab. $$ If ${\mathfrak a}$ is not principal, then ${\mathfrak p}{\mathfrak a} = (a+b\sqrt{-5}\,)$ is, and from $({\mathfrak p}{\mathfrak a})^2 = 2(x+y\sqrt{-5}\,)$ we similarly get $$ x = \pm \frac12(a^2 - 5b^2), \quad y = \pm ab. $$
4. S-Integers
The ring $R = {\mathbb Z}[\sqrt{-5}\,]$ is not a UFD, but $S = R[\frac12]$ is; in fact, $S$ is even norm-Euclidean for the usual norm in $S$ (the norm is the same as in $R$ except that powers of $2$ are dropped). It is also easily seen that $S^\times = \langle -1, 2 \rangle$. From $$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$ and the fact that the factors on the left hand side are coprime we deduce that $x + y\sqrt{-5} = \varepsilon \alpha^2$ for some unit $\varepsilon \in S^\times$ and some $\alpha \in S$. Subsuming squares into $\alpha$ we may assume that $\varepsilon \in \{\pm 1, \pm 2\}$. Setting $\alpha = \frac{a + b\sqrt{-5}}{2^t}$, where we may assume that $a$ and $b$ are not both even, we get $$ x + y \sqrt{-5} = \varepsilon \frac{a^2 - 5b^2 + 2ab\sqrt{-5}}{2^{2t}}. $$ It is easily seen that we must have $t = 0$ and $\varepsilon = \pm 1$ or $t = 1$ and $\varepsilon = \pm 2$; a simple calculation then yields the same formulas as above.
5. Hilbert Class Fields
The Hilbert class field of $K$ is given by $L = K(i)$. It is not too difficult to show that $L$ has class number $1$ (actually it is norm-Euclidean), and that its unit group is generated by $i = \sqrt{-1}$ and $\omega = \frac{1+\sqrt{5}}2$ (we only need to know that these units and their product are not squares). From $$ (x + y\sqrt{-5}\,)(x - y\sqrt{-5}\,) = z^2 $$ and the fact that the factors on the left hand side are coprime in ${\mathcal O}_K$ we deduce that $x + y \sqrt{-5} = \varepsilon \alpha^2$. Subsuming squares into $\alpha^2$ we may assume that $\varepsilon \in \{1, i, \omega, i\omega \}$. Applying the nontrivial automorphism of $L/K$ to $x + y \sqrt{-5} = \varepsilon \alpha^2$ we find $\varepsilon \alpha^2 = \varepsilon' {\alpha'}^2$. Since the ideal ${\mathfrak a} = (\alpha)$ is fixed and since $L/K$ is unramified, the ideal ${\mathfrak a}$ must be an ideal in ${\mathcal O}_K$. Thus either ${\mathfrak a} = (a+b\sqrt{-5}\,)$ is principal in $K$, or ${\mathfrak p} {\mathfrak a} = (a+b\sqrt{-5}\,)$ is; in the second case we observe that ${\mathfrak p} = (1+i)$ becomes principal in ${\mathcal O}_L$.
Thus either $$ x + y \sqrt{-5} = (a+b\sqrt{-5}\,)^2 \quad \text{or} \quad x + y \sqrt{-5} = i \Big(\frac{a+b\sqrt{-5}}{1+i}\,\Big)^2, $$ giving us the same formulas as above.
Avoiding ideal arithmetic in $K$ and only using the fact that ${\mathcal O}_L$ is a UFD seems to complicate the proof even more.
Edit 2 For good measure . . .
6. Hilbert 90
Consider, as above, the equation $X^2 + 5Y^2 = 1$. It shows that the element $X + Y \sqrt{-5}$ has norm $1$; by Hilbert 90, we must have $$ X + Y \sqrt{-5} = \frac{a+b\sqrt{-5}}{a-b\sqrt{-5}} = \frac{a^2 - 5b^2 + 2ab\sqrt{-5}}{a^2 + 5b^2}. $$ Dehomogenizing via $X = \frac xz$ and $Y = \frac yz$ yields the same projective parametrization as above, and we end up with the familiar formulas.
7. Binary Quadratic Forms The equation $x^2 + 5y^2 = z^2$ tells us that the form $Q_0(X,Y) = X^2 + 5Y^2$ with fundamental discriminant $\Delta = -20$ represents a square; this implies that $Q_0$ lies in the principal genus (which is trivial since $Q_0$ is the principal form), and that the representations of $z^2$ by $Q_0$ come from composing representations of $z$ by forms $Q_1$ with $Q_1^2 \sim Q_0$ with themselves.
There are only two forms with discriminant $\Delta$ whose square is equivalent to $Q_0$: the principal form $Q_0$ itself and the form $Q_1(X,Y) = 2X^2 + 2XY + 3Y^2$. Thus either $$ z = Q_0(a,b) = a^2 + 5b^2 \quad \text{or} \quad z = Q_1(a,b) = 2a^2 + 2ab + 3b^2. $$ The formulas for Gauss composition of forms immediately provide us with expressions for $x$ and $y$ in terms of $a$ and $b$, but they can also be checked easily by hand. In the first case, we get $$ x^2 + 5y^2 = (a^2 + 5b^2)^2 = (a^2 - 5b^2)^2 + 5(2ab)^2, $$ and in the second case we can reduce the equations to this one by observing that $2Q_1(a,b) = A^2 + 5b^2$ with $A = 2a+b$, which gives $$ x^2 + 5y^2 = \frac14\Big(A^2 + 5b^2\Big)^2 = \Big(\frac{A^2 - 5b^2}2\Big)^2 + 5(Ab)^2. $$
Your questions would require an enormous amount of work to answer properly, so let me just suggest a few modest and very partial answers to your 1)2)3).
1) Modular forms are shiny: they satisfy or explain many beautiful and surprising numerical identities (about partitions and sums of square among others). This got them noticed in the first place.
2) Modular forms have Galois representations, and conversely Galois representations often come from modular forms. If you care at all about representations of the absolute Galois group of $\mathbb Q$, then you will first presumably be interested in class field theory, and develop the Kronecker-Weber theorem. But then you will get interested in representations of $G_{\mathbb Q}$ of rank 2. Modular forms provide many examples of such Galois representations, and conversely, only a handful of hypotheses are required for such a Galois representation to come from a modular form. This means concretely that one can identify many Galois representations simply by computing a few traces of Frobenius morphisms and then doing some computations in the complex upper half-plane.
3) If a rational elliptic curve has a non-vanishing $L$-function at 1, it has no non-torsion rational points. The main conjecture of Iwasawa (about class groups in the cyclotomic $\mathbb Z_{p}$-extension of $\mathbb Q$) is true. Fermat's last theorem is true. Here are three extremely famous conjectures solved by an ubiquitous appeal to modular forms. All these conjectures were well-known in the 60s but I don't think it is an exaggeration to say that almost no one then would have suspected that modular forms would come into play.
Best Answer
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.