## PRIMES is in P. Where in P?

- Details
- Written by Admin
- Hits: 1563

.

.

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

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