Computing the Ramanujan tau function (Q850530)

The Ramanujan tau function \(\tau(n)\) is completely determined by its values at the primes \(p\) dividing \(n\). It is known that \(|\tau|(n)= O(n^6)\), from which it follows that \(\tau(n)\) can be computed in \(O(\log^3n)\) time provided the factorization of \(n\) and the values of \(\tau(p)\) are known for primes \(p\) dividing \(n\). The author shows that, under the generalized Riemann hypothesis, there is a randomized algorithm to compute \(\tau(p)\) with expected running time \(O(p^{{1\over 2}+ \varepsilon})\) for every \(\varepsilon> 0\), and (without assuming the Riemann hypothesis) there is a deterministic algorithm to compute \(\tau(p)\) in time \(O(p^{{1\over 4}+\varepsilon})\) for every \(\varepsilon> 0\).