Elavult az olvasnivalód. M. Agrawal, N. Kayal and N. Saxena, "PRIMES in P," Ann. of Math. (2), 160:2 (2004) 781–793. http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf

És ahogy NevemTeve helyesen megjegyezte az előzményekre nem teljesen odafigyelve tett megjegyzésemre, a faktorizációról még nem tudjuk. Szokás azt remélni, hogy nem NP-teljes, de még nincs se erre, se arra bizonyíték. Annyit tudunk csak biztosan, hogy NP és co-NP.

Üdv,
Gábor