La base del algoritmo polinómico determinista para la primalidad de Agrawal, Kayal y Saxena es (la versión de grado uno) la siguiente generalización del teorema de Fermat.
Teorema
Supongamos que P es un polinomio con coeficientes enteros y que p es un número primo. Entonces $(P(X))^p\equiv P(X^p)\ (\mod p)$ .
Seguramente este resultado era conocido anteriormente, pero no he podido encontrar una referencia en la literatura sobre el algoritmo AKS (lo que significa que los autores tampoco conocían una referencia). ¿Alguien conoce alguna?
Además, existe un lema inverso al del documento de AKS:
Lema
Si n es un número compuesto, entonces $(X+a)^n\not \equiv X^n+a\ (\mod n)$ siempre que a sea coprima de n.
De nuevo, es fácil generalizar esta afirmación. Por ejemplo, si P es un polinomio que tiene al menos dos coeficientes no nulos y tal que todos los coeficientes no nulos son coprimos a n, entonces $P(X)^n\not\equiv P(X^n)\ (\mod n)$ para el compuesto n.
Por otra parte, es evidente que algunas condiciones son necesarias; por ejemplo $(3X+4)^6\equiv 3X^6+4\ (\mod 6)$ .
¿Existe la mejor declaración posible? Y, de nuevo, ¿hay alguna referencia?
