Calcolatore Numeri Primi

Utilizza questo strumento avanzato per calcolare numeri primi con diversi algoritmi e visualizzare i risultati in tempo reale.

Guida Completa agli Algoritmi per il Calcolo dei Numeri Primi

I numeri primi rappresentano una delle fondamenta della matematica e della crittografia moderna. La loro identificazione efficienti è cruciale per applicazioni che vanno dalla sicurezza informatica alla teoria dei numeri. In questa guida approfondita, esploreremo i principali algoritmi per il calcolo dei numeri primi, analizzandone vantaggi, limiti e implementazioni pratiche.

1. Fondamenti 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).
Distribuzione: I numeri primi diventano meno frequenti all’aumentare dei numeri, ma sono infiniti (dimostrato da Euclide).
Applicazioni: Crittografia (RSA, ECC), generazione di numeri pseudo-casuali, hashing.

2. Algoritmi Deterministici

2.1 Metodo delle Divisioni (Trial Division)

L’algoritmo più semplice per verificare la primalità di un numero n consiste nel testare la divisibilità per tutti gli interi da 2 a √n:

Se n è divisibile per qualsiasi numero in questo intervallo, non è primo.
Altrimenti, è primo.

Complessità: O(√n) – Efficiente solo per numeri piccoli (fino a ~10⁶).

Implementazione:

function isPrimeTrial(n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 === 0 || n % 3 === 0) return false;
    for (let i = 5; i * i <= n; i += 6) {
        if (n % i === 0 || n % (i + 2) === 0) return false;
    }
    return true;
}

2.2 Crivello di Eratostene (Sieve of Eratosthenes)

Algoritmo efficiente per trovare tutti i numeri primi fino a un limite n:

Crea una lista di numeri da 2 a n.
Parti dal primo numero non contrassegnato p (inizialmente 2).
Contrassegna tutti i multipli di p (2p, 3p, ...).
Ripeti fino a √n.

Complessità: O(n log log n) - Ottimale per generare primi fino a ~10⁷.

Vantaggi:

Genera tutti i primi in un intervallo con un'unica esecuzione.
Memoria ottimizzata con bit array.

Algoritmo	Complessità	Limite Pratico	Uso Tipico
Trial Division	O(√n)	~10⁶	Verifica singoli numeri piccoli
Crivello di Eratostene	O(n log log n)	~10⁷	Generazione primi in intervalli
AKS	O(log^7.5 n)	Teorico	Dimostrazione concettuale

3. Algoritmi Probabilistici

3.1 Test di Fermat

Basato sul Piccolo Teorema di Fermat: se p è primo, allora per ogni a coprimo con p, a^p-1 ≡ 1 mod p.

Procedura:

Scegli un a casuale (1 < a < n).
Calcola a^n-1 mod n.
Se ≠ 1, n è composto.
Altrimenti, n è probabilmente primo.

Limiti: Esistono numeri composti (es. 561) che passano il test per tutti gli a coprimi (numeri di Carmichael).

3.2 Test di Miller-Rabin

Versione migliorata del test di Fermat che gestisce i numeri di Carmichael. Complessità: O(k log³ n), dove k è il numero di iterazioni.

Accuratezza:

1 iterazione: accuratezza ≥ 75%.
4 iterazioni: accuratezza ≥ 99.99% per numeri < 2³².
12 iterazioni: accuratezza per tutti i numeri < 2⁶⁴.

Test	Accuratezza (4 iterazioni)	Tempo per n=10⁹	Implementazione
Fermat	~99.5%	0.1 ms	Semplice ma inaffidabile
Miller-Rabin	>99.99%	0.3 ms	Standard industriale
Solovay-Strassen	>99.9%	0.2 ms	Alternativa a Miller-Rabin

4. Algoritmi Avanzati

4.1 Test AKS

Primo algoritmo deterministico in tempo polinomiale (2002), con complessità O(log^7.5 n). Limiti: Pratico solo per numeri molto grandi (>10⁶ cifre) a causa di costanti nascoste elevate.

4.2 Curve Ellittiche (ECPP)

Algoritmo probabilistico basato su curve ellittiche. Vantaggi:

Tempo atteso O(log⁵ n) per numeri fino a 1000 cifre.
Produce un certificato di primalità verificabile.

5. Ottimizzazioni Pratiche

Per implementazioni real-world:

Precalcolo: Memorizza primi piccoli per divisioni rapide.
Bit Array: Nel crivello, usa 1 bit per numero (riduce memoria di 8x).
Segmentazione: Elabora il crivello in blocchi per numeri molto grandi.
Parallelizzazione: Gli algoritmi come il crivello sono facilmente parallelizzabili.

6. Applicazioni nella Crittografia

I numeri primi sono alla base di:

RSA: Chiavi pubbliche/private basate su prodotti di due primi grandi (~1024-4096 bit).
Diffie-Hellman: Scambio di chiavi usando aritmetica modulaire su primi.
Curve Ellittiche (ECC): Primi definiscono il campo finito per le curve.

Requisiti di sicurezza:

Primi per RSA: ≥ 2048 bit (617 cifre decimal).
Primi per ECC: ≥ 256 bit (78 cifre esadecimali).
Deve passare test di primalità con alta certezza (es. 64 iterazioni Miller-Rabin).

7. Benchmark delle Prestazioni

Confrontiamo le prestazioni su un processore moderno (Intel i9-13900K) per un numero a 64 bit:

Algoritmo	Tempo (μs)	Memoria (KB)	Note
Trial Division	120,000	1	Non pratico per 64 bit
Miller-Rabin (10 iter)	45	2	Standard per crittografia
Baillie-PSW	60	3	Nessun falso positivo noto
AKS	1,200,000	500	Solo teorico

8. Risorse Accademiche

Per approfondimenti:

Corso su Teoria dei Numeri - UC Berkeley: Tratta algoritmi di primalità con dimostrazioni rigorose.
NIST Cryptographic Standards: Linee guida per la generazione di primi in crittografia.
The Prime Pages - University of Tennessee at Martin: Database di record e risorse sui numeri primi.

9. Implementazione in Linguaggi Moderni

Esempio in Python usando gmpy2 per numeri molto grandi:

import gmpy2
from gmpy2 import is_prime

def generate_large_prime(bits=2048):
    while True:
        p = gmpy2.mpz_random(gmpy2.random_state(), bits)
        p |= 1  # Assicura che sia dispari
        if is_prime(p, 256):  # 256 iterazioni Miller-Rabin
            return p

# Genera due primi per RSA
p = generate_large_prime(1024)
q = generate_large_prime(1024)
n = p * q

10. Errori Comuni e Best Practice

Errori:

Usare trial division per numeri > 10⁶.
Non verificare i divisori fino a √n (es. fermarsi a n/2).
Ignorare i numeri di Carmichael nei test probabilistici.
Non ottimizzare il crivello con bit array per grandi n.

Best Practice:

Per numeri < 10⁶: Crivello di Eratostene segmentato.
Per numeri 64-bit: Miller-Rabin con 10-20 iterazioni.
Per crittografia: Usare librerie testate (OpenSSL, GMP).
Validare sempre i risultati con più algoritmi per applicazioni critiche.

11. Frontiere della Ricerca

Aree attive di studio:

Algoritmi quantistici: L'algoritmo di Shor (1994) fattorizza numeri in tempo polinomiale su un computer quantistico, minacciando RSA.
Primi generalizzati: Estensioni in anelli di numeri algebrici.
Test di primalità deterministici: Migliorare AKS per applicazioni pratiche.
Distribuzione dei primi: Approssimazioni più precise della funzione π(n).

Algoritmi Calcolo Nuneri Primi