Why are elliptic curves important for elementary number theory?

Elliptic curves (or even Abelian varieties) are useful tools for many high-falutin' reasons

1. They can be used to construct $\ell$-adic Galois representations
2. One can find automorphic forms from an elliptic curve fairly easily
3. There is a nice way to find formal group laws using elliptic curves
4. Families of elliptic curves provide nice geometric examples for various cohomological phenomena

But, I have yet to learn why they they are important from an elementary number-theoretic perspective. Why did early mathematicians "run into" elliptic curves and abelian varieties to begin with and how are they useful for elementary number theory?

• The historical origins of elliptic curves have nothing to do with number theory. Rather they arose from the study of so-called "elliptic integrals" by Euler and others. See en.wikipedia.org/wiki/Elliptic_integral for some explanation; the basic point to notice is that the integrands $R$ are naturally defined on some elliptic curve $y^2=P(x)$. If I remember correctly there is some more discussion of the connection in the "Historical Sketch" section of Shafarevich v2; surely standard texts on elliptic curves (eg Silverman) have some of the same material --- not to mention this website! – bertram Jun 1 '17 at 20:36
• From my understanding a lot of the machinery for elliptic curves can be generalized to abelian varieties and abelian varieties can be thought of devices which contain the arithmetic information for smooth projective varieties (since 1-motives generate the category of motives and every abelian variety is isogenous to the jacobian of some curve, and the motive of some variety contains all relevant arithmetic information...) – 54321user Dec 5 '17 at 0:34
• Although elliptic curves weren't first encountered in a number theoretic context (see @bertram 's comment) they're a natural thing to talk about at the end of a first course in number theory. The capstone of that course is usually quadratic reciprocity - i.e. quadratic forms and second degree diophantine equations. Then elliptic curves start the study of third degree equations. Silbverman's book does just that. – Ethan Bolker Apr 15 '18 at 20:17
• Are elliptic curves elementary, anyway? – Oscar Lanzi Aug 30 '20 at 12:41

I am unsure of the early motivations for studying elliptic curves, so I will leave that discussion for another to answer.

At any rate, integer factorization is one of the most important problems in applied number theory, and elliptic curves facilitate a sub-exponential factorization algorithm, discovered in 1985 by Hendrik Lenstra.

As you probably already know, the points $(x,y)$ that solve the elliptic curve over a given field can be endowed with a group structure. The algorithm takes advantage of this fact and proceeds as follows:

• Choose a number $n \in \mathbb{N}$ to be factored.
• Choose a random elliptic curve $E(\mathbb{Z}_n)$ and a point $P \in E$.
• Choose a smooth number $e \in \mathbb{N}$. $m!$ for a small $m$ is a common choice.
• Compute $eP$. As we do this, the way addition has been defined forces us to compute the inverse of an element modulo $n$, which can be done via the Euclidean algorithm. As we proceed with this step, there are three scenarios we can encounter:

• All the calculations could be done since the inverse mentioned above was able to be computed with each addition. In this case, go back to the second bullet above and repeat the whole process with a new elliptic curve.

• We arrive at $kP = \infty$ for some $k \leq e$. If this happens, go to the second bullet above and repeat.

• We arrive at an addition that could not be computed because the inverse of an element $k \in \mathbb{Z}_n$ did not exist. If this happens, $k$ and $n$ are not coprime, which means $k$ is a nontrivial factor of $n$.

Also, if we count cryptography as a subset of (applied) number theory, then one can also use the group provided by an elliptic curve to carry out discrete-log-based asymmetric cryptosystems like Diffie-Hellman or digital signature schemes like ECDSA. The advantage here is that there are no known algorithms for solving the elliptic curve discrete log problem in sub-exponential time, unlike the $\mathbb{Z}_p$ setting.