PRIMES is in P. Where in P?

  • Print
User Rating: / 1
PoorBest 
Details
Written by Admin
Hits: 201

.

.

In 2002-2003 Agrawal, Kayal, and Saxena in a great breakthrough "PRIMES is in P"   ( Wiki EN ) proved that the PRIMES function (prime number test)  is O(log ^8 n), in other words polynomial of degree 8 of the number of digits (log n) of a given number n.

Congratulations Smile

BTW, where in P is its real position? Any idea?

 

 

 

 

Notice that the Prime Number Test

PRIMES(n) = "n is/not a prime number"

does not solve the Integer Factorization Problem

IFP(x) = "x is/not pq, for integers p, q>1" .

 

For complexity of many problems check great pages ( Wiki EN, Wiki EN, EN, EN, EN ).

Submit PRIMES is in P. Where in P? in Delicious Submit PRIMES is in P. Where in P? in Digg Submit PRIMES is in P. Where in P? in FaceBook Submit PRIMES is in P. Where in P? in Google Bookmarks Submit PRIMES is in P. Where in P? in Stumbleupon Submit PRIMES is in P. Where in P? in Technorati Submit PRIMES is in P. Where in P? in Twitter Submit PRIMES is in P. Where in P? in Twitter