1,066
edits
Changes
Jump to navigation
Jump to search
Line 44:
Line 44: + + + +
→Since this article is currently protected...: new section
Please fix the incorrect statement about the NP-completeness of prime factorization. In fact, prime factorization is ''known'' not to be in NPC unless P=NP. --[[User:DiogenesTonne|DiogenesTonne]] 17:59, 22 April 2009 (EDT)
Please fix the incorrect statement about the NP-completeness of prime factorization. In fact, prime factorization is ''known'' not to be in NPC unless P=NP. --[[User:DiogenesTonne|DiogenesTonne]] 17:59, 22 April 2009 (EDT)
== Since this article is currently protected... ==
You can't have an article on primes that discusses primality testing and doesn't mention Agrawal's algorithm. There needs to be a mention of the AKS test which allows primality testing in polynomial time. This was a big deal. [[User:JoshuaZ|JoshuaZ]] 20:49, 22 April 2009 (EDT)