12 ms·
No. 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
by enth 16y ago
No. 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)?