The hardness of computing an eigenform
Abstract
Description
In this article, we give evidence that computing Fourier coefficients of the Hecke eigenforms for composite indices is no easier than factoring integers. In particular, we show that the existence of a polynomial time algorithm that, given n, computes the n-th Fourier coefficient of a (fixed) Hecke eigenform implies that we can factor most RSA moduli (numbers that are products of two distinct primes) in polynomial time.
5 Pages (corrected a typo in statement of Theorem 2.1)
5 Pages (corrected a typo in statement of Theorem 2.1)