Crivello di Atkin
# Crivello di Atkin

Il crivello di Atkin è un algoritmo matematico veloce e moderno per trovare tutti i numeri primi fino a uno specifico valore intero. È una versione ottimizzata dell'antico crivello di Eratostene: il crivello di Atkin compie del lavoro preliminare, poi segna non tutti i multipli dei primi, ma i multipli dei quadrati dei primi. Fu creato da A. O. L. Atkin e Daniel J. Bernstein.

## Algoritmo

Nell'algoritmo:

* tutti i resti sono classi di resto in modulo sessanta (si divide il numero per 60 e si guarda il resto);
* tutti i numeri, inclusi x e y, sono interi e positivi;
* alternare un elemento nella lista del crivello, significa cambiare il valore (primo o non_primo) nel valore opposto.

I passi sono:

* creare una lista dei risultati, composta di 2, 3, e 5;
* creare una lista del crivello con un elemento per ogni numero intero positivo; tutti gli elementi di questa lista devono avere valore non_primo;
* per ogni elemento nella lista del crivello:
   * se l'elemento è un numero con resto 1, 13, 17, 29, 37, 41, 49, o 53, alternarla un numero di volte uguale alle possibili soluzioni di $4x^2$ + $y^2$ = numero_dell'elemento;
   * se l'elemento è un numero con resto 7, 19, 31, o 43, alternarla un numero di volte uguale alle possibili soluzioni di $3x^2$ + $y^2$ = numero_dell'elemento;
   * se l'elemento è un numero con resto 11, 23, 47, o 59, alternarla un numero di volte uguale alle possibili soluzioni di $3x^2$ - $y^2$ = numero_dell'elemento con x > y;
   * se l'elemento ha qualche altro resto, ignorarlo completamente;
* cominciare con il numero più piccolo della lista del crivello;
* prendere il prossimo numero con valore primo della lista del crivello;
* aggiungere questo numero alla lista dei risultati;
* effettuare il quadrato del numero, e assegnare a tutti i multipli del quadrato il "flag" non_primo;
* ripetere i passaggi da 5 a 8.

Il punto 3 si può anche eseguire al contrario, provando tutti i valori di x e y e alternando l'elemento corrispondente a $4x^2$ + $y^2,$ $3x^2$ + $y^2$ e $3x^2$ $-y^2$ se il risultato ha resto pari a quello indicato nella descrizione qui sopra.

## Pseudocodice

Quanto segue è lo pseudocodice per una versione semplice dell'algoritmo:

Notare che questo pseudocodice è più lento rispetto al crivello di Eratostene. Per migliorare la sua efficienza, bisogna usare un metodo più veloce per la soluzione delle tre equazioni quadratiche. È possibile utilizzare a tale scopo l'identità $(x+1)^{2}=x^{2}+2x+1$ per non calcolare i quadrati di x e y, e calcolare il modulo delle tre funzioni quadratiche a partire dal modulo di x e y come nelle seguenti tabelle:

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

| 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^{2}+y^{2}$

| 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^{2}-y^{2}$

| 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 |

## Spiegazione

L'algoritmo ignora completamente tutti i numeri divisibili per due, tre o cinque. Tutti i numeri che in modulo 60 hanno resto 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 sono divisibili per due e non sono quindi primi. Tutti i numeri che in modulo 60 hanno resto 3, 9, 15, 21, 27, 33, 39, 45, 51, o 57 sono divisibili per tre e quindi non sono primi. Tutti i numeri che in modulo 60 hanno resto 5, 25, 35 o 55 sono divisibili per cinque e quindi non sono primi. Tutti questi resti vengono quindi ignorati. Rimangono i numeri che, modulo 12, hanno resto pari a 1, 5, 7, 11.

Tutti i numeri che in modulo 60 hanno resto 1, 13, 17, 29, 37, 41, 49, o 53 hanno in modulo 4 un resto uguale a 1 (1 o 5 modulo 12; se il resto fosse 9 sarebbero divisibili per 3). Questi numeri sono primi se e solo se il numero di soluzioni di $4x^2$ + $y^2$ = n è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.1 in).

Tutti i numeri che in modulo 60 hanno resto 7, 19, 31 o 43 hanno in modulo 6 un resto uguale a 1 (1 o 7 modulo 12). Questi numeri sono primi se e solo se il numero di soluzioni di $3x^2$ + $y^2$ = n è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.2 in).

Tutti i numeri che in modulo 60 hanno resto 11, 23, 47 o 59 hanno in modulo 12 un resto uguale a 11. Questi numeri sono primi se e solo se il numero di soluzioni di $3x^2$ − $y^2$ = n è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.3 in).

Nessun potenziale numero primo è divisibile per 2, 3 o 5 quindi non possono essere divisibili neanche per i loro quadrati. Ecco perché il controllo squarefree non include $2^2,$ $3^2,$ e $5^2.$

## Complessità computazionale

Il crivello calcola primi fino a N con O(N/log log N) operazioni e soltanto $N^{1/2+o(1)}$ bit di memoria. Il crivello di Eratostene compie O(N) operazioni e necessita di $O(N^{1/2}(log$ log N)/log N) bit di memoria.

