[15595] in cryptography@c2.net mail archive
Re: Claimed proof of the Riemann Hypothesis released
daemon@ATHENA.MIT.EDU (Ivan Krstic)
Thu Jun 10 08:41:47 2004
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Thu, 10 Jun 2004 01:50:22 -0400
From: Ivan Krstic <krstic@fas.harvard.edu>
To: cryptography@metzdowd.com
In-Reply-To: <87ekoojvrw.fsf@snark.piermont.com>
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@metzdowd.com
