Claimed proof of the Riemann Hypothesis released

[Ivan Krstic]

Perry E. Metzger wrote:
 > Actual practical impact on cryptography? Likely zero, even if it turns
 > out the proof is correct (which of course we don't know yet), but it
 > still is neat for math geeks.

Right. He constrains his proof to dealing with a specific subset of 
Dirichlet zeta functions, which means he's not proving GRH or ERH, the 
former of which would have some - mostly theoretical - implications on 
crypto in the sense that it would make a number of primality algorithms, 
previously running in "assumed P", provably polynomial-time. Even if he 
proved GRH, I don't think the implications for crypto would be 
particularly great -- yes, things like Miller-Rabin would provably run 
in O(ln(n)^4), but AKS already runs in provably-polynomial time without 
dependencies on unproved theorems, and has been improved to comparable 
speed: O(ln(n)^k) | k=4+epsilon for certain cases, upper bound 
k=6+epsilon [1], possibly faster since the last time I looked.

Cheers,
Ivan.

[1] See Crandall, Papadopoulos: "On the implementation of AKS-class 
primality tests" (March 2003)

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com