4 ms·
> I'll wait for the day when he announces he's broken it. And so will a massive part of the Computer Science/Mathematics/Physics community. Answering the P vs
by sebkomianos 16y ago
> I'll wait for the day when he announces he's broken it.
And so will a massive part of the Computer Science/Mathematics/Physics community. Answering the P vs NP question is kind of a big deal. :D
- enth 16y agoNo. Integer factorization is not NP-hard (so not NP-complete). (This isn't proven, but it's generally thought to be the case.) So, while doing a polynomial-time integer factorization would be hugely significant (and make all asymmetric encryption in the world useless), it would not prove P=NP.
- kragen 16y ago> So, while doing a polynomial-time integer factorization would be hugely significant (and make all asymmetric encryption in the world useless) This is wrong in two ways. First, a polynomial-time algorithm could still be too slow to be practical, either because the degree of the polynomial were high or because the constant factor or asymptotically disappearing overhead were high. Second, discrete-logarithm-based cryptography does not depend on the difficulty of integer factorization. That includes Diffie-Hellman, ElGamal, DSA, SRP, and elliptic-curve methods. You're right that integer factorization is not known to be NP-hard, and so a polynomial-time integer factorization algorithm wouldn't show P=NP.
- enth 16y agoYou're right, that statement was rather too broad. Thank you for the correction.
- sebkomianos 16y agoI don't want to turn this into a complexity theory discussion thread but isn't it an NP problem? And does proving that it can be solved in polynomial time mean P == NP (and vice versa)?