Computational aspects of modular forms and elliptic curves.

摘要

In this thesis I investigate certain computational aspects of Modular Forms and Elliptic Curves. The main computational problem in the theory of Modular Forms is the computation of their Fourier coefficients. The first part of the thesis is concerned with the computational complexity of this problem. I show that if we do not fix the modular form, then the problem of computing Fourier coefficients is ♯ P -hard. Next, in joint work with Eric Bach, we show that if we fix a modular form that is a Hecke eigenform, then computing the Fourier coefficients is at least as hard as factoring RSA moduli. I also provide a new algorithm to compute the Fourier coefficients of any fixed space of cusp forms. This algorithm has a faster asymptotic running time than any previous algorithm for computing Fourier coefficients of these forms.; The arithmetic theory of Elliptic Curves has many interesting computational problems. I study two such problems in this thesis. One is the problem of distinguishing elliptic curves with Complex Multiplication from ordinary elliptic curves. I give two algorithms for this problem: one is a randomized polynomial time algorithm and the other is a deterministic polynomial time algorithm. I also show how the randomized polynomial time algorithm can be made to have one-sided error. The other problem that I study is the problem of computing the modular polynomial. The modular polynomial is an object that governs isogenies between elliptic curves. In joint work with Kristin Lauter, we provide a new algorithm to compute the modular polynomial over finite fields. This algorithm also yields an efficient method of generating random isogenies from an elliptic curve over a finite field.