The hardness of computing an eigenform

MaRDI QIDQ3533254zbMATH OpenFDO

Authors Eric Bach, Denis Xavier Charles

Publication date 23 October 2008

Full work available at URL https://arxiv.org/abs/0708.1192

zbMATH Keywords

computational complexitycomputing Fourier coefficients of Hecke eigenformsRamanujan tau function

Mathematics Subject Classification ID

Fourier coefficients of automorphic forms (11F30) Analytic computations (11Y35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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.

Cited in

(2)

• Counting lattice vectors
• Sets of Linear Forms Which Are Hard to Compute

This page was built for publication: The hardness of computing an eigenform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3533254)