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]
Algoritmo
Así funciona el algoritmo:
- Todos los restos son módulo 60, es decir, se divide el número entre 60 y se toma el resto.
- Todos los números, incluidos x e y, son enteros positivos.
- Invertir un elemento de la lista de la criba significa cambiar el valor ("primo" o "no primo") al valor opuesto.
- Crear una lista de resultados, compuesta por 2, 3 y 5.
- Crear una lista de la criba con una entrada por cada entero positivo; todas las entradas deben marcarse inicialmente como "no primos".
- Para cada entrada en la lista de la criba:
- Si la entrada es un número con resto 1, 13, 17, 29, 37, 41, 49 o 53, se invierte tantas veces como soluciones posibles hay para 4x2 + y2 = entrada.
- Si la entrada es un número con resto 7, 19, 31 o 43, se invierte tantas veces como soluciones posibles hay para 3x2 + y2 = entrada.
- Si la entrada es un número con resto 11, 23, 47 o 59, se invierte tantas veces como soluciones posibles hay para 3x2 - y2 = entrada con la restricción x > y.
- Si la entrada tiene otro resto, se ignora.
- Se empieza con el menor número de la lista de la criba.
- Se toma el siguiente número de la lista de la criba marcado como "primo".
- Se incluye el número en la lista de resultados.
- Se eleva el número al cuadrado y se marcan todos los múltiplos de ese cuadrado como "no primos".
- Repetir los pasos 5 a 8.
Pseudocódigo
Este pseudocódigo indica una versión sencilla del algoritmo:
// límite arbitrario de búsqueda límite ← 1000000 // inicializar la criba es_primo(i) ← falso, i ∈ [5, límite] // introducir candidatos a números primos: // números naturales con un número impar de // representaciones en determinadas formas cuadráticas para (x, y) en [1, √límite] × [1, √límite]: n ← 4x²+y² si (n ≤ límite) ∧ (n mod 12 = 1 ∨ n mod 12 = 5): es_primo(n) ← ¬es_primo(n) n ← 3x²+y² si (n ≤ límite) ∧ (n mod 12 = 7): es_primo(n) ← ¬es_primo(n) n ← 3x²-y² si (x > y) ∧ (n ≤ límite) ∧ (n mod 12 = 11): es_primo(n) ← ¬es_primo(n) // eliminar compuestos mediante la criba para n en [5, √límite]: si es_primo(n): // n es primo, se omiten los múltiplos de su cuadrado, esto es // suficiente porque los números compuestos que están // en esta lista no pueden ser [[número libre de cuadrados|libres de cuadrados]] es_primo(k) ← falso, k ∈ {n², 2n², 3n², ..., limit} escribir 2, 3 para n en [5, límite]: si es_prime(n): escribir n
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 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:
y\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 |
1 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |
2 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
3 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 |
4 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |
6 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 | 0 | 4 | 4 |
7 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |
8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
9 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 | 9 | 1 | 1 |
10 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 | 4 | 8 | 8 |
11 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 | 1 | 5 | 5 |
y\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
1 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |
2 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
3 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 |
4 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
5 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |
6 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
7 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |
8 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
9 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 | 9 | 0 |
10 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 | 4 | 7 |
11 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 | 1 | 4 |
y\x | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
1 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |
2 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
3 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 |
4 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
5 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |
6 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 | 0 | 3 |
7 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |
8 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
9 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 | 3 | 6 |
10 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 | 8 | 11 |
11 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 | 11 | 2 |
Explicación
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 4x2 + y2 = 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 3x2 + y2 = 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 3x2 − y2 = 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 22, 32 y 52.
Complejidad computacional
Esta criba obtiene los números primos hasta N mediante O(N/log log N) operaciones con solamente N1/2+o(1) bits de memoria. Esto es ligeramente mejor que la criba de Eratóstenes, que requiere O(N) operaciones y O(N1/2(log log N)/log N) bits de memoria.[1] Estas complejidades computacionales asintóticas ya incluyen algunas optimizaciones sencillas.
Apéndice
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.
Referencias
- ↑ a b c d e A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.[1] (en inglés)
Enlaces externos
- Una Implementación sencilla de la criba (en C++ y Maple) (en inglés)
- Una implementación optimizada de la criba (en C) (en inglés)
- Implementación sencilla de la criba (en C) (en portugués)
Datos: Q1542201