[Math] Why are elliptic curves important for elementary number theory

abelian-varietieselementary-number-theoryelliptic-curvesnumber 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?

Best Answer

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$.

Read more about why this works.

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.

Related Question