Barrapunto

a) Los algoritmos de factorización incluyen tests de primalidad, por lo tanto un buen algoritmo para determinar rápidamente si un numero es primo o no también es importante para los problemas de factorización.

b) Lo de nlog(n) no es válido para los tests de proposito general, aplicables tanto a números pequeños como grandes, puede que sea válido para algún subconjunto particular, o para números pequeños. Además la función logaritmica está siempre por debajo de y=x para valores de la base mayores que 1, eso quiere decir que n < nlog(n) < n*n. Está entre la función lineal y la cuadrática. De hecho es el tiempo medio para el algoritmo quick-sort.

Para que queden más claras las cosas ahí van algunos datos:
- 1983. Algoritmo determinista. (log n)^O(log log log n)
- 1986. Algoritmo probabilistico basado en curvas elipticas. Tiempo polinomial.

El algoritmo del que estamos hablando es universal, incondicional, determinista y Ô((log n)^12), es decir sitúa el chequeo de primalidad dentro de P, lo hace por primera vez en la historia y además lo hace de una forma simple y elegante: se deriva del teorema chino del resto.

Por último una referencia básica sobre los tests de primalidad, aparte de la propia publicación

Nada menos.