6 ms·
> Almost exactly 2 decades ago a related theorem, prime factorisation being in P, was proved by a couple of undergrads working with a professor in IIT Kanpur, I
by q-big 4y ago
> Almost exactly 2 decades ago a related theorem, prime factorisation being in P, was proved by a couple of undergrads working with a professor in IIT Kanpur, India
It is still an open problem whether prime factorization is in P or not. What Manindra Agrawal, Neeraj Kayal and Nitin Saxena showed is that checking whether a given (binary) number is prime is in P. Up to today, no polynomial-time method has been published to obtain a non-trivial factor of the input if the AKS algorithm returns that it is not prime.
- vishnugupta 4y agoOops; 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
- woojoo666 4y ago> What Manindra Agrawal, Neeraj Kayal and Nitin Saxena showed is that checking whether a given (binary) number is prime is in P. Wow this confused the hell out of me because I thought, isn't the sieve of eratosthenes already below polynomial time? But from what I read, while the sieve of eratosthenes is sub-polynomial relative to the magnitude of the input, the AKS method is polynomial time relative to the length of the input in binary representation (aka the number of binary digits).
- kadoban 4y agoYou're far from the first person to be confused by this, if it helps. https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time
- lupire 4y agoThat's funny because "most" NP-complete problems are pseudo-polynomial, because a simple exponential problem is O(e^polynomial), so log of that is polynomial. But people forget that natural numbers are just data, and that data can be interpreted at a a natural number.