Criba de Atkin

Criba de Atkin

Saltar a navegación, búsqueda

La criba de Atkin es un algoritmo rápido y moderno empleado en matemáticas 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.

1. Crear una lista de resultados, compuesta por 2, 3 y 5.
2. Crear una lista de la criba con una entrada por cada entero positivo; todas las entradas deben marcarse inicialmente como "no primos".
3. 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 ó 53, se invierte tantas veces como soluciones posibles hay para 4x² + y² = entrada.
   • Si la entrada es un número con resto 7, 19, 31 ó 43, se invierte tantas veces como soluciones posibles hay para 3x² + y² = entrada.
   • Si la entrada es un número con resto 11, 23, 47 ó 59, se invierte tantas veces como soluciones posibles hay para 3x² - y² = entrada con la restricción x > y.
   • Si la entrada tiene otro resto, se ignora.
4. Se empieza con el menor número de la lista de la criba.
5. Se toma el siguiente número de la lista de la criba marcado como "primo".
6. Se incluye el número en la lista de resultados.
7. Se eleva el número al cuadrado y se marcan todos los múltiplos de ese cuadrado como "no primos".
8. 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 (x + 1)² = x² + 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:

4x² + y²

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

3x² + y²

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

3x² − y²

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 ó 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 ó 58 son pares y por tanto compuestos. Los de resto 3, 9, 15, 21, 27, 33, 39, 45, 51 ó 57 son divisibles por 3 y por tanto compuestos. Finalmente, los de resto 5, 25, 35 ó 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 ó 53 tienen un resto, módulo 4, de 1. Estos números son primos si y sólo 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 ó 43 tienen un resto, módulo 6, de 1. Estos números son primos si y sólo 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 ó 59 tienen un resto, módulo 12, de 11. Estos números son primos si y sólo 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 ó 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².

Complejidad computacional

Esta criba obtiene los números primos hasta N mediante O(N/log log N) operaciones con sólo 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.

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

1. ↑ ^{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 optimizada de la criba (en C) (en inglés)
• Implementación en Python (en inglés)
• Implementación sencilla de la criba (en C) (en portugués)

Obtenido de "Criba de Atkin"