| Let f be a modular form of even weight k and level N which is a normalized eigen-form for the Hecke operators, and write [special characters omitted] for its Fourier expansion at iinfinity. We assume the Fourier coefficients {af(n)}(infinity/n=1 are rational integers. A notable example of such a form is Ramanujan's cusp form Delta of weight 12 and level 1. In this case, the Fourier coefficients are given by the famous Ramanujan tau function: [special characters omitted].;In this thesis, we study applications of the Fourier coefficients tau( n), and more generally, af( n).;First, we present a factoring algorithm that uses an oracle that outputs af(n) . We show that the algorithm runs in polynomial time for squarefree integers on average, and quasi-polynomial time for non-squarefree integers on average. We note that current factoring algorithms have sub-exponential runtimes. More importantly, when combined with Edixhoven's (conditional) polynomial time algorithm for computing af(p), we get an equivalence between factoring and computing af(n) .;Secondly, we present an algorithm that uses an oracle that outputs af(n) for testing the squarefree-ness of an integer. This algorithm exploits the greatest common divisor of sequences of the form (af(pr)) r∈A where p is a prime and A ⊂ N . Thirdly, we present a primality testing algorithm that uses an oracle that outputs tau( n) and af/E}(n) where fE is a form of weight 2 corresponding to an elliptic curve. As a corollary, we use such an oracle to compute in polynomial time the value of the Mobius function in the squarefree case. |
