Prime Factorization

views:

599

answers:

+8 Q:

Prime Factorization

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.

+6 A:

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.

Konrad Rudolph 2009-11-12 21:05:19

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).

chrisg 2009-11-12 21:10:03

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

S.Lott 2009-11-12 21:10:59

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.

walkytalky 2009-11-12 21:22:49

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 =)

Stephen Canon 2009-11-12 21:24:03

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.

David Thornley 2009-11-12 21:37:56

@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.

Konrad Rudolph 2009-11-12 21:47:36

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.

Eclipse 2009-11-12 21:58:53

"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 ;-)

Steve Jessop 2009-11-12 22:46:48

+3 A:

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.

Bill the Lizard 2009-11-12 21:10:23

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.

chrisg 2009-11-12 21:18:28

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.

Loadmaster 2009-11-12 22:43:17

"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.

Steve Jessop 2009-11-12 22:51:56

+2 A:

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.

Austin Salonen 2009-11-12 21:12:29

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.

chrisg 2009-11-12 21:25:12

+3 A:

erickson 2009-11-12 21:34:56

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

Konrad Rudolph 2009-11-12 22:05:32

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.

erickson 2009-11-12 22:26:36

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? http://www.schneier.com/essay-198.html

rmeador 2009-11-12 22:38:16

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.

erickson 2009-11-12 23:21:15

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.

Paul 2009-11-30 20:10:37

"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.

erickson 2009-11-30 20:47:22

+2 A:

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.

plinth 2009-11-12 21:39:11

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

ldog 2009-11-12 22:02:16

@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.

David Thornley 2009-11-12 22:06:39

@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.

ldog 2009-11-13 17:49:56

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

Agor 2009-11-16 04:34:48

+1 A:

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.

Keith Randall 2009-11-12 22:16:50

ansaurus

tags:

views:

answers:

Prime Factorization

related questions