News for hackers. Stuff that matters.
Re:GetACoder.com: Solve P Vs NP by voidpointer on Monday August 16, 2010 @10:49AM (#1607909)
Does that include factoring large prime numbers? If a good approximation would exist for that, wouldn't that make public-key encryption pretty useless?
Re:GetACoder.com: Solve P Vs NP by jerf on Monday August 16, 2010 @11:22AM (#1608025)
Included in that handwave about probability distributions was a caveat about not being handed pathological instances of problems. Encryption harnesses pathological instances and wouldn't be covered by such a handwave.

(Is there ever any other reason to generate multi-hundred digit numbers and try to factor them? Honest question, if anybody's got a fun answer, though I am asking about something actually useful that you know about, not something hypothetical.)

Re:GetACoder.com: Solve P Vs NP by eru on Monday August 16, 2010 @12:21PM (#1608233)
Actually, it's quite hard to come up with good primes for RSA. They need to avoid lots of properties, because researches have found efficient attacks on numbers with those properties.
Re:GetACoder.com: Solve P Vs NP by eru on Monday August 16, 2010 @12:20PM (#1608223)
Factoring numbers is already suspected to be much easier than NP-complete.

That is because factoring prime numbers is in the intersection between NP and co-NP. Co-NP is the set of problems where a "NO" answer is easily checkable with a certificate. If NP ?= co-NP is as much a question as P ?= NP. (I.e. no known proof either way, but every expects them to be unequal.)

Re:GetACoder.com: Solve P Vs NP by amalcon on Monday August 16, 2010 @10:59AM (#1607941)
Public-key encryption schemes would simply need to avoid reasonable circumstances. I suspect "product of two large primes" falls outside the "reasonable circumstances" for factoring.
Re:GetACoder.com: Solve P Vs NP by eru on Monday August 16, 2010 @12:24PM (#1608236)
It's even harder than that. There are lots of known attacks, if you are not careful with your choice of prime numbers. (`Careful' is equal to `choosing pathological instances'.)