News for hackers. Stuff that matters.
Re:What if P = NP? by bdhe on Friday April 01, 2011 @06:03PM (#2398278)
> Factorization is indeed in NP. It might also be in P. I should've said "based on the idea that" instead of "the fact that."

I'll reiterate. It is unknown if factorization is currently NP-hard. UKNOWN. It is most likely NOT NP-hard otherwise there would be huge implications in Complexity Theory.

It suffices for crypto for problems to be hard on an average. Factoring a random product of two large primes is hard. Factoring is probably not NP hard because no one knows if a factoring algorithm will help solve SAT.

Re:What if P = NP? by presidentender on Friday April 01, 2011 @06:33PM (#2398386)
NP is a superset of P.
Re:What if P = NP? by bdhe on Friday April 01, 2011 @10:27PM (#2398914)
I think I was mistaken in understanding what you said. Yes, factoring is in NP, but it is not known to be NP-hard. Being in NP doesn't automatically imply its usefulness in Crypto (because, as you say, P is a subset of NP). Neither does the NP-hardness of a problem automatically imply its usefulness. Crypto seems to need these weird problems that are not always NP-hard, yet, in some sense, harder than NP-hard problems. You can think of it as: crypto => P != NP, but not vice-versa.