Criba de Atkin

La criba de Atkin es un algoritmo rápido y moderno empleado en matemática para hallar todos los números primos menores o iguales que un número natural dado. Es una versión optimizada de la criba de Eratóstenes, pero realiza algo de trabajo preliminar y no tacha los múltiplos de los números primos, sino concretamente los múltiplos de los cuadrados de los primos. Fue ideada por A. O. L. Atkin y Daniel J. Bernstein.^[1]​

Así funciona el algoritmo:

Este pseudocódigo indica una versión sencilla del algoritmo:

Este pseudocódigo está así escrito para aumentar la claridad, pero los cálculos redundantes hacen que sea más lento que la criba de Eratóstenes. Para mejorar su eficiencia, se deben emplear métodos más rápidos para hallar las soluciones de las tres ecuaciones. Para ello, se puede utilizar la identidad ${displaystyle (x+1)^{2}=x^{2}+2x+1}$ para no tener que calcular el cuadrado de x e y, y calcular el módulo de las tres funciones cuadráticas a partir del módulo de x e y, tal como viene en las siguientes tablas:

${displaystyle 4x^{2}+y^{2}}$

${displaystyle 3x^{2}+y^{2}}$

${displaystyle 3x^{2}-y^{2}}$

El algoritmo ignora cualquier número divisible por 2, 3 o 5. Todos los números con resto, módulo 60, igual a 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 48, 50, 52, 54, 56 o 58 son pares y por tanto compuestos. Los de resto 3, 9, 15, 21, 27, 33, 39, 45, 51 o 57 son divisibles por 3 y por tanto compuestos. Finalmente, los de resto 5, 25, 35 o 55 son divisibles entre 5 y por tanto compuestos. Todos estos restos son ignorados.

Todos los números con resto, módulo 60, igual a 1, 13, 17, 29, 37, 41, 49 o 53 tienen un resto, módulo 4, de 1. Estos números son primos si y solamente si el número de soluciones de 4x² + y² = n es impar y el número es libre de cuadrados (demostrado como "teorema 6.1" en^[1]​).

Todos los números con resto, módulo 60, igual a 7, 19, 31 o 43 tienen un resto, módulo 6, de 1. Estos números son primos si y solamente si el número de soluciones de 3x² + y² = n es impar y el número es libre de cuadrados (demostrado como "teorema 6.2" en^[1]​).

Todos los números con resto, módulo 60, de 11, 23, 47 o 59 tienen un resto, módulo 12, de 11. Estos números son primos si y solamente si el número de soluciones de 3x² − y² = n es impar y el número es libre de cuadrados (demostrado como "teorema 6.3" en^[1]​).

Ninguno de los candidatos a primos es divisible entre 2, 3 o 5, por lo que no puede ser divisible entre sus cuadrados. Esta es la razón por la que las comprobaciones de si un número es libre de cuadrados no incluyen los casos 2², 3² y 5².

Esta criba obtiene los números primos hasta N mediante O(N/log log N) operaciones con solamente N^1/2+o(1) bits de memoria. Esto es ligeramente mejor que la criba de Eratóstenes, que requiere O(N) operaciones y O(N^1/2(log log N)/log N) bits de memoria.^[1]​ Estas complejidades computacionales asintóticas ya incluyen algunas optimizaciones sencillas.

Las dos primeras ecuaciones que se utilizan para determinar la primalidad de un número tras sus comprobaciones modulares son ecuaciones de elipses. Pueden reescribirse en la forma estándar dividiendo los dos miembros de la ecuación entre n, donde n es la entrada cuya primalidad se quiere determinar. Esta forma facilitaría la implementación de un test.