Riemann Hypothesis and Computational Complexity

A commenter asks a good question for a bad reason: Would a proof of the Riemann Hypothesis have any impact on complexity theory?

Rather surprisingly the answer is yes, particularly in the area of computational number theory. In the most famous example, Gary Miller in 1975 gave a polynomial-time algorithm for primality whose correctness could be proven by assuming the Extended Riemann Hypothesis (ERH). Of course in 2002 we had a polynomial-time primality algorithm with no assumption. However the original analysis of the algorithm gave a constant which depends on how ERH is resolved.

There are still many other problems in computational number theory that require ERH. For example, according to Eric Bach, the only polynomial-time algorithm computing square roots modulo p, when p is large relies on ERH. "The idea is to combine an algorithm that uses a quadratic nonresidue, such as Shanks's algorithm (this in Knuth v. 2 I am pretty sure) with a bound on the least quadratic nonresidue mod p (e.g. in my thesis it is proved to be <= 2 (ln p)^2 if ERH is true)."