Prime Factorization

Question

I have recently been reading about the general use of prime factors within cryptography. Everywhere i read, it states that there is no 'PUBLISHED' algorithm which operates in polynomial time (as opposed to exponential time), to find the prime factors of a key.

If an algorithm was discovered or published which did operate in polynomial time, then how would this impact in the real world computing environment as opposed to the world of theory and computer science. Considering the extent we depend on cryptography would the would suddenly come to halt.

With this in mind if P = NP is true, what might happen, how much do we depend on the fact that it is yet uproved.

I'm a beginner so please forgive any mistakes in my question, but i think you'll get my general gist.

Turbosupercharger

Should be community wiki. Maybe also a better candidate for mathoverflow.net – Acceptor

How can move it, are you able to it or let me know how to, thanks chris. – Turbosupercharger

Questions could be migrated to serverfault or superuser from here. For mathoverflow.net I think you'll have to sign up for an account and post the question there (I don't think it's affiliated with this site). – Acceptor

Seems to be a mixture of mathematics and conspiracy theory. (In general, no mathematical discovery can be kept under wraps very long, so it would be best to drop the conspiracy theory.) – Curriery

I just peeked in at mathoverflow.net. I don't think this question would go over any better there. They seem to favor the hard stuff. BTW, you could ask this question anywhere you've got an account. It could be moved there by enough people with 3K+ rep or one moderator. – Curriery

@David Thornley: We must not let the masses know about the irrationality of the square root of two! – Stere

@David Thornley: true, on second thought I agree on the 'probably also does not belong on mathoverflow.net' statement. – Acceptor

I have to say, I don't understand how this is non-programming related. The question boils down to "what real-world algorithmic problems would be affected if P = NP" which seems like a perfectly reasonable question. – Pamplona

This belongs squarely in computer science. – Startling

Answer 1

If a truly efficient algorithm for factoring composite numbers was discovered, I think the biggest immediate impact would be on e-commerce. Specifically, it would grind to a halt until a form of encryption was developed that doesn't rely on factoring being a one-way function.

There has been a lot of research into cryptography in the private sector for the past four decades. This was a big switch from the previous era, where crypto was largely in the purview of the military and secret government agencies. Those secret agencies definitely tried to resist this change, but once knowledge is discovered, it's very hard to keep it under wraps. With that in mind, I don't think a solution to the P = NP problem would remain a secret for long, despite any ramifications it might have in this one area. The potential benefits would be in a much wider range of applications.

Incidentally, there has been some research into quantum cryptography, which

relies on the foundations of quantum mechanics, in contrast to traditional public key cryptography which relies on the computational difficulty of certain mathematical functions, and cannot provide any indication of eavesdropping or guarantee of key security.

The first practical network using this technology went online in 2008.

Stere

Thanks, thats what im after, how much does the real world depend on this and what might happen, im not a conspiracy therorist, but there are surely those who could reak havock if such an alogrthm where found. – Turbosupercharger

You're talking only about the public-key (PKI) portion of crypto. The symmetric encryption algorithms (e.g., AES) don't use prime numbers. But there are a few alternative asymmetric-key algorithms, they just are not commercially popular. – Demi

"it would grind to a halt until a form of encryption was developed that doesn't rely on factoring being a one-way function". ECC, for example. Assuming that this factorisation breakthrough doesn't also solve the discrete logarithm problem. – Anesthesiology

-1: It would not grind to a halt; there are existing crypto methods that do not rely on difficulty of either factorization or the discrete log (which would almost certainly be broken if factorization was, though I don't know of an explicit reduction). – Galvez

Answer 2

With this in mind if N = NP is true, would they ever tell us.

Who are “they”? If it were true, we would know. The computer scientists? That’s us. The cryptographers and mathematicians? The professionals? The experts? People like us. Users of the Internet, even of Stack Overflow.

We wouldn’t need being told. We’d tell.

Science and research isn’t done behind closed doors. If someone finds out that P = NP, this couldn’t be kept secret, simply because of the way that research is published. In principle, everyone has access to such research.

Medrek

The good guys, whoever discovered it, as oposed to terrorists, end of the world types. I understand what you mean i jsut couldnt think of a better way to express it. if n = np was proved to be true it would nessesarily be a good think, concidering the extent to which security depends on it (at the moment). – Turbosupercharger

+1: Who are "they" anyway? I've wondered about that for a long time. – Wilkens

This is the scientific ideal, but it isn't the only way research can be done. A method or proof could still work even if it isn't published in peer reviewed journals. While there will be relatively few organisations with the resources to do serious research behind closed doors, I'm pretty sure that crypto is an area many of those organisations are interested in. – Radborne

The NSA most certainly does research behind closed doors, and it's not at all clear that they would publish such a result. I'm sure it would leak out eventually, but you never know =) – Bulky

The NSA hires a lot of good mathematicians to work on crypto, and seems to stay ahead of academia on crypto matters (although the only people who really know aren't talking). This would be a whole lot bigger than crypto. If the NSA could swing it, academics couldn't be far behind. – Curriery

@Stephen, David: even the NSA uses RFPs to design their cryptography algorithms because they realize that they cannot keep all the bright minds behind closed doors. So yes, the military does research behind closed doors, as do many big companies. But I believe that all the really groundbreaking work cannot be kept secret. As for the claim that the NSA is “ahead” of public research, I rather doubt it. Their resources, though vast, are simply too limited to compete with “basically all the rest”, except on very small problems. – Medrek

Another thing to note, is the ease of leaking an algorithm vs. other conspiracy ideas. If, for example, the military had captured an alien, there's almost no bit of evidence that is going to convince everyone (even physical evidence is going to be doubted). On the other hand, if someone has an algorithm to factor a number in polynomial time, no further proof is needed - it either works, or it doesn't. – Ingaingaberg

"it either works, or it doesn't" - although you'd need the proof that it's polynomial, as well as the algorithm. For instance, I can easily give you an algorithm which factors numbers in polynomial time if and only if any algorithm exists which does so. But if indeed that algorithm does run in polynomial time, then the proof that it does is formidable. Bearing in mind that there are people who believe you can square the circle, convincing everyone is pretty much unattainable ;-) – Anesthesiology

Answer 3

It depends on who discovers it.

NSA and other organizations that research cryptography under state sponsorship, contrary to Konrad's assertion, do research and science behind closed doors—and guns. And they have "scooped" published academic researchers on some important discoveries. Finally, they have a history of withholding cryptanalytic advances for years after they are independently discovered by academic researchers.

I'm not big into conspiracy theories. But I'd be very surprised if a lot of "black" money hasn't been spent by governments on the factorization problem. And if any results are obtained, they would be kept secret. A lot of criticism has been leveled at agencies in the U.S. for failing to coordinate with each other to avert terrorism. It might be that notifying the FBI of information gathered by the NSA would reveal "too much" about the NSA's capabilities.

You might find the first question posed to Bruce Schneier in this interview interesting. The upshot is that NSA will always have an edge over academia, but that margin is shrinking.

For what it is worth, the NSA recommends the use of elliptic curve Diffie-Hellman key agreement, not RSA encryption. Do they like the smaller keys? Are they looking ahead to quantum computing? Or … ?

Lecroy

+1 actually. But I stand by my remark in the comments below. ;-) – Medrek

I agree with the principle that keeping mathematical truths hidden for long is not possible. But while it lasts, a secret like that is a valuable card that any state would play carefully. – Lecroy

IIRC, the elliptic curve algorithm published by the NSA was discovered to have a something that could be a back door, so maybe that's why they were pushing its use? schneier.com/essay-198.html – Judd

That's not a flaw in EC key agreement, but it is a flaw in the RNG recommended by the NSA. But it's a great illustration; both that the NSA might selectively conceal or reveal cryptanalytic results, and that academia often independently discovers the same result within a few years. – Lecroy

P = NP has far reaching consequences well beyond cryptography. If proven, we'd know. It one of the biggest, if not the biggest, open question in computer science today. – Millet

"We'd know?" How? We'd have to be told by whoever discovers it. And some of the people who are most likely to discover it have some reasons not to disclose it immediately. – Lecroy

Answer 4

Keep in mind that factoring is not known to be (and is conjectured not to be) NP-complete, thus demonstrating a P algorithm for factoring will not imply P=NP. Presumably we could switch the foundation of our encryption algorithms to some NP-complete problem instead.

Contributory

Answer 5

Here's an article about P = NP from the ACM: http://cacm.acm.org/magazines/2009/9/38904-the-status-of-the-p-versus-np-problem/fulltext

From the link:

Many focus on the negative, that if P = NP then public-key cryptography becomes impossible. True, but what we will gain from P = NP will make the whole Internet look like a footnote in history.

Since all the NP-complete optimization problems become easy, everything will be much more efficient. Transportation of all forms will be scheduled optimally to move people and goods around quicker and cheaper. Manufacturers can improve their production to increase speed and create less waste. And I'm just scratching the surface.

Given this quote, I'm sure they would tell the world.

I think there were researchers in Canada(?) that were having good luck factoring large numbers with GPUs (or clusters of GPUs). It doesn't mean they were factored in polynomial time but the chip architecture was more favorable to factorization.

Griddlecake

I didnt know other people focused on this, its just an observation i made, im just trying to find out how much we actually depend on the fact n = np is unproved. – Turbosupercharger

Answer 6

As a side note, if you enter into the realm of quantum computing, you can factor in polynomial time. See Rob Pike's notes from his talk on quantum computing, page 25, also known as Shor's algorithm.

Metameric

I think quantum computers will make the question of N=NP obsolete before anyone proves P=NP or proves its not. – Hendel

@gmatt: Nope; there's a lot of useful NP things that, apparently, quantum computers won't be able to do. Moreover, it gets really hard to make quantum computers with lots of qubits, and while factoring 15 was an impressive achievement considering everything it can be easily duplicated with modern conventional computers. I don't know if quantum computers will ever actually be useful. – Curriery

@David: really? thats surprising to me, I thought that the class of problems NP, and P are such that if you can solve any problem in that class, then every other problem can be solved using the same algorithm. – Hendel

gmatt: Factoring is in NP, but also co-NP. It is a weird problem, here is the wiki page: en.wikipedia.org/wiki/Integer_factorization – Fishbein

@ldog: If you solve one NP-complete problem in polynomial time, you've solved them all. But quantum computers are not known or believed to be able to solve any NP-complete problems. Look up complexity class BQP for information on what could be solved efficiently. Shor's algorithm and Grover's algorithm are the best-known. – Galvez