4 ms·
Oops; you are right. If my memory serves right, showing prime factorisation in P will imply P == NP; which would have been a sensational news at a different lev
by vishnugupta 4y ago
Oops; you are right. If my memory serves right, showing prime factorisation in P will imply P == NP; which would have been a sensational news at a different level altogether.
- Ar-Curunir 4y agoNo, factoring being in P would not imply P == NP. Factoring is not NP-hard.
- Laakeri 4y agoWell, it is also not proved to not be NP-hard, so it could also be NP-hard to our current knowledge. But you are right that researchers believe that it's not NP-hard.
- Ar-Curunir 4y agoGood catch, you’re right, nobody has yet proven that factoring is NP-hard, but a ton of evidence indicates that it is highly unlikely to be NP-hard
- q-big 4y ago> showing prime factorisation in P will imply P == NP Whether "Factorization is in P" actually implies "P=NP" is another open problem (most researchers in this area don't believe that this is the case). What does hold is that if we found a "fast" algorithm for factorization, this would break some cryptosystems. The most well-known example is RSA, but other, more academic cryptosystems would be broken, too. In its "Public key cryptography" template (https://en.wikipedia.org/wiki/Template:Cryptography_public-key https://en.wikipedia.org/wiki/Template:Cryptography_public-k...; click "[show]"), Wikipedia lists the following cryptosystems to be dependent on the hardness of integer factorization: * Benaloh * Blum–Goldwasser * Cayley–Purser * Damgård–Jurik * GMR * Goldwasser–Micali * Naccache–Stern * Paillier * Rabin * RSA * Okamoto–Uchiyama * Schmidt–Samoa