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.[1]
Algoritmo
modificaNell'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 4x2 + y2 = 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 3x2 + y2 = 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 3x2 - y2 = 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 4x2 + y2, 3x2 + y2 e 3x2 -y2 se il risultato ha resto pari a quello indicato nella descrizione qui sopra.
Pseudocodice
modificaQuanto segue è lo pseudocodice per una versione semplice dell'algoritmo:
limit = 1000000; // Limite arbitrario di ricerca
array is_prime[5:limit] initial false; // Array del crivello
biginteger x,y,n,k; // Dev'essere capace di contenere 5*limit: 4x^2 + y^2!
// put in candidate primes: integers which have an odd number of representations by certain quadratic forms.
for x:=1:sqrt(limit) do
for y:=1:sqrt(limit) do
n:=4x^2 + y^2; if n <= limit and n mod 12 = 1 or 5 then is_prime[n]:=not is_prime[n];
n:=3x^2 + y^2; if n <= limit and n mod 12 = 7 then is_prime[n]:=not is_prime[n];
n:=3x^2 - y^2; if n <= limit and x > y and n mod 12 = 11 then is_prime[n]:=not is_prime[n];
next y;
next x;
// Eliminazione dei numeri non primi setacciando i risultati rimanenti
// Se n è primo, elimina tutti i multipli del suo quadrato; i numeri
// composti che sono rimasti nella lista devono avere fattori primi
// con esponente pari.
for n:=5:sqrt(limit) do
if is_prime[n] then for k:=n^2:limit:n^2 do is_prime[k]:=false; next k;
next n;
// Presentazione dei risultati
print 2, 3; for n:= 5:limit do if is_prime[n] then print n; next n;
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à 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[senza fonte]:
| 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 |
Spiegazione
modificaL'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 4x2 + y2 = n è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.1 in [1]).
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 3x2 + y2 = n è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.2 in [1]).
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 3x2 − y2 = n è dispari ed il numero è privo di quadrati (dimostrato come teorema 6.3 in [1]).
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 22, 32, e 52.
Complessità computazionale
modificaIl crivello calcola primi fino a N con O(N/log log N) operazioni e soltanto N1/2+o(1) bit di memoria. Il crivello di Eratostene compie O(N) operazioni e necessita di O(N1/2(log log N)/log N) bit di memoria.[2]
Note
modifica- ^ a b c d A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, https://cr.yp.to/papers/primesieves-19990826.pdf (1999). [Accessibile a tutti]
A.O.L. Atkin, D.J. Bernstein, Prime sieves using binary quadratic forms, Math. Comp. 73 (2004), 1023-1030. [Più recente] - ^ Queste stime di complessità includono alcune semplici ottimizzazioni, come la wheel factorization, e la divisione in blocchi computazionali più piccoli.
