Computing the Ramanujan tau function

We show that the Ramanujan tau function τ(n) can be computed by a randomized algorithm that runs in time for every O( ) assuming the Generalized Riemann Hypothesis. The same method also yields a deterministic algorithm that runs in time O( ) (without any assumptions) for every ε > 0 to compute τ(n). Previous algorithms to compute τ(n) require Ω(n) time. Research supported in part by NSF grant CCR-9988202 2000 Mathematics Subject Classification Primary—11-04; Secondary—11Y55, 11F11