News for hackers. Stuff that matters.
Re:Why 256 bit keys are large enough by jessaustin on Monday December 17, 2012 @04:24PM (#4934465)
"an NP-but-non-P problem"

Maybe I'm misunderstanding but if you had one of these you would have answered a fairly important question in CS theory. Perhaps you mean to say "NP-complete", but even then I'm not sure the proposition is correct.

Re:Why 256 bit keys are large enough by amalcon on Monday December 17, 2012 @05:54PM (#4934975)
You're right that my statement wasn't specific enough; I was going for brevity. The precise statement is: You need a problem with a known polynomial-time nondeterministic algorithm, but no known polynomial-time deterministic algorithm.
Re:Why 256 bit keys are large enough by ReidZB on Monday December 17, 2012 @06:36PM (#4935169)
A very important point though: public-key cryptosystems rely on one-way functions, functions that are hard to invert in the average case, NOT just the worst case, which is not your typical complexity-theory mindset. So, I would be careful when talking about complexity classes in the context of crypto because it can be very, very easy to trip up and say something that's either not comprehensive or just downright incorrect.
Re:Why 256 bit keys are large enough by Dylan16807 on Monday December 17, 2012 @04:41PM (#4934554)
It's closer to "NP-but-not-weaker". NP-complete also means you can convert other NP problems into them, which isn't necessary.