4 ms·
> 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
by bdhe 16y ago
> 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.
- presidentender 16y agoNP is a superset of P.
- bdhe 16y agoI 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.