Implications of Riemann Hypothesis variants in TCS

Question

The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a reference to a conditional result in TCS based on the Riemann hypothesis. I am therefore wondering,

what are the major implications of the Riemann hypothesis in TCS?

As a start here is an example from a recent paper, Homomorphism Polynomials complete for VP by Durand, Mahajan, Malod, de Rugy-Altherre, and Saurab. From the paper's introduction:

One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, [3]).

Answer 1

First, I’m not aware of any CS application of Riemann’s hypothesis as such. There are various applications of generalizations of RH.

Second, a terminological note: contrary to popular belief, there is no such thing as “the generalized Riemann hypothesis” or “the extended Riemann hypothesis”. Both of these terms are used more-or-less interchangeably in the literature as a loose denotation of any kind of generalizations of the RH to some class of $L$-functions. They have no fixed specific meaning, or at least none consistent across papers of different authors (or even different papers of the same author).

The result mentioned in the OP is based on a result of Koiran that the existential theory of $\mathbb C$ (which commonly goes under the confusing name “Hilbert’s Nullstellensatz”) is in AM, and therefore in the polynomial hierarchy. It assumes the RH for Dedekind $\zeta$-functions; specifically, it relies on an effective version of the Chebotarev density theorem.

Another class of CS applications exploit the fact that every nontrivial quadratic Dirichlet character modulo $m$ assumes $\chi(x)=-1$ for some $x=O((\log m)^2)$, originally due to Ankeny, often stated with a reference to Bach who improved the constant in the $O$-notation. It relies on the RH for $L$-functions of quadratic Dirichlet characters, which is weaker than the one for Dedekind $\zeta$-functions. (The result actually holds more generally for finite-order Hecke characters, and in full generality it needs the RH for $L$-functions of said Hecke characters, which is in fact equivalent to the RH for Dedekind $\zeta$-functions. However, the CS applications I’m aware of do not need this.) The consequences are that one can derandomize several algorithms, such as the Miller–Rabin primality testing algorithm, or the Shanks–Tonelli algorithm for computing square roots modulo primes.

As far as I know, RH is not useful to deterministically find primes in a given interval, as alluded to in a comment above. This would follow from Cramér’s conjecture or a similar bound on prime gaps, but the RH is too weak to prove such bounds (the error term in the prime number theorem is at least of order roughly $\sqrt x$ no matter what).

Answer 2

Assuming an extended Riemann Hypothesis, L. M. Adleman and H. W. Lenstra gave a polynomial time algorithm to find an irreducible polynomial of a desired degree over a finite field: http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf