Calcolatore di Numeri Primi
Utilizza questo strumento avanzato per generare e analizzare tabelle di numeri primi con diversi algoritmi di calcolo.
Guida Completa agli Algoritmi per il Calcolo delle Tabelle di Numeri Primi
I numeri primi rappresentano una delle fondamenta della teoria dei numeri e della crittografia moderna. La loro distribuzione apparentemente casuale ma profondamente strutturata ha affascinato matematici per secoli. Questo articolo esplora gli algoritmi più efficienti per generare tabelle di numeri primi, con particolare attenzione alle implementazioni pratiche e alle ottimizzazioni.
1. Fondamenti Teorici dei Numeri Primi
Un numero primo è un numero naturale maggiore di 1 che ha esattamente due divisori distinti: 1 e sé stesso. Le proprietà fondamentali includono:
- Teorema Fondamentale dell’Aritmetica: Ogni numero intero maggiore di 1 è un numero primo o può essere rappresentato come prodotto di numeri primi in modo unico (a meno dell’ordine dei fattori).
- Infinitudine dei Primi: Dimostrata da Euclide nel 300 a.C., afferma che esistono infiniti numeri primi.
- Distribuzione Asintotica: Il teorema dei numeri primi afferma che la densità dei primi intorno a un numero grande n è circa 1/ln(n).
2. Algoritmi Classici per la Generazione di Numeri Primi
2.1 Divisione per Tentativi (Trial Division)
L’algoritmo più semplice ma meno efficiente:
- Per verificare se n è primo, dividere n per tutti gli interi da 2 a √n.
- Se nessuna divisione dà resto zero, n è primo.
Complessità: O(√n) per numero, O(n√n) per generare tutti i primi fino a n.
Ottimizzazioni:
- Verificare solo divisori primi fino a √n.
- Saltare i numeri pari (eccetto 2).
- Terminare anticipatamente se viene trovato un divisore.
2.2 Crivello di Eratostene
Algoritmo efficiente per generare tutti i primi fino a un limite n:
- Crea una lista di numeri da 2 a n.
- Parti dal primo numero p = 2.
- Elimina tutti i multipli di p maggiori di p stesso.
- Trova il prossimo numero non eliminato e ripeti dal passo 3.
Complessità: O(n log log n) – quasi lineare per grandi n.
Ottimizzazioni:
- Crivello segmentato per memoria limitata.
- Bit array invece di array di boolean.
- Saltare i multipli pari (eccetto 2).
2.3 Crivello di Sundaram
Variante del crivello di Eratostene che genera solo numeri dispari:
- Elimina i numeri della forma i + j + 2ij dove 1 ≤ i ≤ j.
- I numeri rimanenti della forma 2k + 1 sono primi.
Vantaggi: Elimina automaticamente tutti i numeri pari, riducendo lo spazio di memoria.
3. Algoritmi Probabilistici e Moderni
3.1 Test di Primalità Miller-Rabin
Test probabilistico per determinare se un numero è (probabilmente) primo:
- Scrivi n-1 come d·2s.
- Scegli un numero a casuale tra 2 e n-2.
- Calcola x ≡ ad mod n.
- Se x ≡ 1 o x ≡ n-1, n passa il test.
- Altrimenti, eleva x al quadrato fino a s-1 volte.
Accuratezza: Con k iterazioni, la probabilità di errore è ≤ 4-k.
3.2 Crivello Quadratico e Crivello sul Campo dei Numeri
Algoritmi avanzati per la fattorizzazione di grandi numeri, utilizzati in crittografia:
- Crivello Quadratico: Basato sulla ricerca di quadrati congruenti modulo n.
- Crivello sul Campo dei Numeri (NFS): Il più efficiente per numeri > 100 cifre.
4. Confronto delle Prestazioni
La seguente tabella confronta le prestazioni degli algoritmi per generare tutti i primi fino a n:
| Algoritmo | Complessità | Memoria | Ottimale per | Tempo per n=106 (ms) |
|---|---|---|---|---|
| Divisione per Tentativi | O(n√n) | O(1) | Singoli test di primalità | ~12000 |
| Crivello di Eratostene | O(n log log n) | O(n) | Generazione di tabelle fino a 107 | ~45 |
| Crivello di Sundaram | O(n log n) | O(n) | Generazione di primi dispari | ~60 |
| Miller-Rabin (k=20) | O(k log3n) | O(1) | Numeri molto grandi (>1015) | N/A (singoli test) |
5. Ottimizzazioni Pratiche
Per implementazioni reali, considerare:
- Precalcolo: Memorizzare primi piccoli per test rapidi.
- Parallelizzazione: Il crivello di Eratostene è facilmente parallelizzabile.
- Memoria Efficiente: Usare bit array o strutture dati compatte.
- Algoritmi Ibridi: Combinare crivello per numeri piccoli e test probabilistici per numeri grandi.
6. Applicazioni nella Crittografia
I numeri primi sono fondamentali in:
- RSA: Basato sulla difficoltà di fattorizzare il prodotto di due grandi primi.
- Diffie-Hellman: Utilizza primi per generare chiavi condivise.
7. Limiti Teorici e Problemi Aperti
Nonostante i progressi, rimangono sfide aperte:
- Ipotesi di Riemann: Collegata alla distribuzione asintotica dei primi.
- Primi Gemelli: Non si sa se esistano infiniti primi p tali che p+2 sia primo.
- Primi di Mersenne: La ricerca di primi della forma 2p-1 è ancora attiva (progetto GIMPS).