Cryptocurrency cruncher cranks prime number constellation Bitcoin mining, our own Simon Rockman wrote last January, “is essentially a brute-force attack on the generating algorithm”. “Bitcoin, and all the other alt-coins, is training a skillset for building password-cracking hardware that is both powerful and portable,” he wrote. It looks like cryptocurrencies are also helping to …
A solution would be HUGELY disruptive to security.
If I remember correctly, the solution allows any NP problem to be mapped to a P problem. (or allows it to be proved that it's impossible for any NP to map to P). The NSA would pay north of a billion for a solution that implied the former, I'm sure. As long as it was undisclosed to anyone else, natch.
No, that's the P vs NP problem, which is about whether there exist polynomial-time solutions to problems such as the travelling salesman. The Riemann Hypothesis is about the distribution of zeroes of the Riemann Zeta function, which is intimately linked to the distribution of primes. Virtually everyone believes that P and NP are distinct, and that the RH is true, but solving one of them has really nothing to do with solving the other. Proving P=NP (which most people in the field think is unlikely) *might* help improve factorization, which has implications for cryptography, but that wouldn't help with RH. Likewise, proving RH (which virtually every mathematician believes is true) is unlikely to have any impact on P vs NP.
Proving P=NP (which most people in the field think is unlikely) *might* help improve factorization, which has implications for cryptography,
More precisely, proving P=NP proves there are no trapdoor functions - that is, that there are no functions for which verifying a result is significantly easier than computing that result. (That's pretty much the definition of NP: it's the class of problems that have worse-than-polynomial time but can be checked in polynomial time.)
Such a proof would invalidate all asymmetric-cryptography systems, since they're based on asymmetric work factors, and for similar reasons invalidate the basis for all cryptocurrencies. If the proof were by construction, or otherwise showed a practical solution to a general NP problem in feasible P time (i.e., the polynomial had reasonable exponents), then asymmetric cryptography and crypocurrencies would be immediately broken in practice, since converting one NP problem to another in P time is always possible and often straightforward.
So, yeah, some implications for cryptography. Fortunately it looks very unlikely that P=NP.
but that wouldn't help with RH.
Agreed.
The Register 
Biting the hand that feeds IT
Copyright. All rights reserved © 1998–2024
