Garbell de Atkin

El garbell de Atkin és un algoritme ràpit i modern empleat en matemàtica per a trobar tots els número primo menors o iguals que un número natural donat. És una versió optimisada de la garbell de Eratóstenes, pero realisa una miqueta de treball preliminar i no tacha els múltiples dels número primo, sino concretament els múltiples dels quadrats dels cosins. Va ser ideada per A. O. L. Atkin i Daniel J. Bernstein.^[1]

Algoritme

Aixina funciona l'algoritme:

Tots els restants són mòdul 60, és dir, es dividix el número entre 60 i es pren el restant.
Tots els números, inclosos x i i, són sancers positius.
Invertir un element de la llista del garbell significa canviar el valor ("primer" o "no primer") al valor opost.

Crear una llista de resultats, composta per 2, 3 i 5.
Crear una llista del garbell en una entrada per cada sancer positiu; totes les entrades deuen marcar-se inicialment com "no primers".
Per a cada entrada en la llista del garbell:
- Si l'entrada és un número en restant 1, 13, 17, 29, 37, 41, 49 o 53, s'invertix tantes voltes com a solucions possibles hi ha per a 4x² + i² = entrada.
- Si l'entrada és un número en restant 7, 19, 31 o 43, s'invertix tantes voltes com a solucions possibles hi ha per a 3x² + i² = entrada.
- Si l'entrada és un número en restant 11, 23, 47 o 59, s'invertix tantes voltes com a solucions possibles hi ha per a 3x² - i² = entrada en la restricció x > i.
- Si l'entrada té un atre restant, s'ignora.
S'escomença en el menor número de la llista del garbell.
Es pren el següent número de la llista del garbell marcat com "primer".
S'inclou el número en la llista de resultats.
S'eleva el número al quadrat i es marquen tots els múltiples d'eixe quadrat com "no primers".
Repetir els passos 5 a 8.

Pseudocódigo

Este pseudocódigo indica una versió senzilla de l'algoritme:

// llímit arbitrari de busca
llímit ← 1000000         

// inicializar el garbell
és_primer(i) ← fals, i ∈ [5, llímit] 

// introduir candidats a número primo: 
// número natural en un número impar de //
representacions en determinades formes quadràtiques
para (x, i) en [1, √llímit] × [1, √llímit]:
    n ← 4x²+i²
    si (n ≤ llímit) ∧ (n mod 12 = 1 ∨ n mod 12 = 5):
        és_primer(n) ← ¬és_primer(n)
    n ← 3x²+i²
    si (n ≤ llímit) ∧ (n mod 12 = 7):
        és_primer(n) ← ¬és_primer(n)
    n ← 3x²-i²
    si (x > i) ∧ (n ≤ llímit) ∧ (n mod 12 = 11):
        és_primer(n) ← ¬és_primer(n)
  
// eliminar composts per mig del garbell
per a n en [5, √llímit]:
    si és_primer(n):
        // n és primer, s'ometen els múltiples del seu quadrat, açò és
        // suficient perque els número compuesto que estan
        // en esta llista no poden ser [[número lliure de quadrats|lliures de quadrats]]
        és_primer(k) ← fals, k ∈ {n², 2n², 3n², ..., limit} 

escriure 2, 3
per a n en [5, llímit]:
    si és_prime(n): escriure n

Este pseudocódigo està aixina escrit per a aumentar la claritat, pero els càlculs redundantes fan que siga més llent que el garbell de Eratóstenes. Per a millorar la seua eficiència, es deuen amprar métodos més ràpits per a trobar les solucions de les tres equacions. Per a això, es pot utilisar l'identitat $(x + 1)^{2} = x^{2} + 2 x + 1$ per a no tindre que calcular el quadrat de x i i, i calcular el mòdul de les tres funcions quadràtiques a partir del mòdul de x i i, tal com ve en les següents taules:

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

ix	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

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

ix	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

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

ix	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

Referències

↑ A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.[1] (en anglés)

Referències

Este artícul conté una traducció derivada de «Criba de Atkin» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.

[paper-1] A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030.[1] (en anglés)

[1]