Hacker News Reader

Comment by q-big | Hacker News Reader

> 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.

View on HN

> 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).

You're far from the first person to be confused by this, if it helps.

https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time

That'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.

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.

No, factoring being in P would not imply P == NP. Factoring is not NP-hard.

Well, 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.

Good 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

> 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-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

Reply on news.ycombinator.com