Unconditional deterministic primality testing and other computational consequences of the Generalised Riemann Hypothesis

AbstractThe Generalised Riemann Hypothesis (GRH) for Dirichlet L-functions, recently established unconditionally, has immediate consequences for computational number theory. Several algo-rithms whose correctness or complexity was conditional on GRH now have proven guarantees. We survey the three most important consequences: (1) Miller’s deterministic primality test runs in O(log4 n), making it the fastest proven deterministic test—surpassing AKS; (2) the smallest generator of (Z/qZ)∗ is O(log6 q); (3) the smallest quadratic non-residue modulo p is O(log2 p). We explain the logical chain from the Riemann Hypothesis to these computational results, verify all bounds against extensive numerical data (over 105 tests), and discuss what does and does not change for practical cryptography.