Comment

Comment by q-big

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

parent q-big 4 years ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton