Algoritmi Calcolo Numeri Primi

Guida Completa agli Algoritmi per il Calcolo dei Numeri Primi

I numeri primi rappresentano uno dei concetti fondamentali della teoria dei numeri e della matematica computazionale. La loro importanza spazia dalla crittografia moderna (come nell’algoritmo RSA) alla teoria dei numeri pura. In questa guida esploreremo i principali algoritmi per identificare e generare numeri primi, analizzandone complessità computazionale, vantaggi e limitazioni.

1. Definizione e Proprietà Fondamentali dei Numeri Primi

Un numero primo è un numero naturale maggiore di 1 che ha esattamente due divisori distinti: 1 e sé stesso. Le proprietà chiave includono:

• Teorema Fondamentale dell’Aritmetica: Ogni numero intero maggiore di 1 è un numero primo oppure può essere rappresentato come prodotto di numeri primi (fattorizzazione unica).
• Infinitudine: Euclide dimostrò che esistono infiniti numeri primi (circa 300 a.C.).
• Distribuzione: Il Teorema dei Numeri Primi descrive la distribuzione asintotica dei primi.

2. Algoritmi Deterministici per il Test di Primalità

2.1 Metodo delle Divisioni (Trial Division)

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

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

Complessità	Vantaggi	Limitazioni
O(√n)	Semplice da implementare	Lento per numeri grandi (es. > 10^6)

2.2 Crivello di Eratostene (Sieve of Eratosthenes)

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

1. Crea una lista di numeri da 2 a n.
2. Parti dal primo numero non cancellato (p) e cancella tutti i suoi multipli.
3. Ripeti fino a raggiungere √n.

Complessità	Ottimizzazioni	Uso Tipico
O(n log log n)	Segmented Sieve per memoria	Generazione di primi fino a 10^7-10^8

3. Algoritmi Probabilistici

3.1 Test di Miller-Rabin

Un test probabilistico che determina se un numero è probabilmente primo. Per un numero dispari n > 2:

1. Scrivi n-1 come d·2^s.
2. Scegli un numero a casuale (2 ≤ a ≤ n-2).
3. Verifica se a^d ≡ 1 mod n oppure a^d·2r ≡ -1 mod n per qualche 0 ≤ r < s.

Se n passa il test per k valori di a, la probabilità che sia composto è ≤ 4^-k. Per n < 2⁶⁴, i valori {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37} sono sufficienti per un test deterministico (Baillie-PSW).

3.2 Confronto con il Test di Fermat

Il test di Fermat (basato sul Piccolo Teorema di Fermat) è meno affidabile perché esistono i numeri di Carmichael che lo superano pur essendo composti. Miller-Rabin è preferibile per la sua maggiore accuratezza.

4. Algoritmi Avanzati

4.1 Test AKS (Agrawal-Kayal-Saxena)

Primo algoritmo deterministico in tempo polinomiale (2002), con complessità O(log^7.5 n). Nonostante la teoria rivoluzionaria, è meno efficiente in pratica rispetto a Miller-Rabin per numeri < 10²⁰.

4.2 Curve Ellittiche (ECPP)

Il test Elliptic Curve Primality Proving è il metodo più efficiente per numeri molto grandi (es. > 10¹⁰⁰). Si basa sulla teoria delle curve ellittiche e produce una certificato di primalità verificabile.

5. Applicazioni Pratiche

• Crittografia: RSA, Diffie-Hellman, e ECC richiedono numeri primi grandi (es. 2048-bit).
• Teoria dei Numeri: Congettura di Goldbach, ipotesi di Riemann.
• Informatica: Generazione di hash, testing di hardware (es. Great Internet Mersenne Prime Search).

6. Ottimizzazioni e Implementazioni

Per migliorare le prestazioni:

• Precalcolo: Usa il crivello per generare primi piccoli e memorizzarli.
• Parallellizzazione: Il crivello e Miller-Rabin sono facilmente parallelizzabili.
• Librerie: Utilizza GMP (GNU Multiple Precision) per aritmetica su grandi numeri.

7. Benchmark e Confronto Prestazionale

Algoritmo	Tempo per n=10^6	Tempo per n=10^18	Memoria
Trial Division	~1 ms	~1000 s	O(1)
Sieve of Eratosthenes	~5 ms	N/A (memoria)	O(n)
Miller-Rabin (k=5)	~0.1 ms	~0.5 ms	O(1)

Per numeri estremamente grandi (es. 10¹⁰⁰), ECPP è l’unico metodo pratico, con tempi dell’ordine dei minuti su hardware moderno.

8. Risorse Accademiche e Approfondimenti

Per approfondire:

• Primality Testing (MIT) – Analisi dettagliata di Miller-Rabin e AKS.
• Stanford – Primality Testing – Confronto tra algoritmi probabilistici e deterministici.
• The Prime Pages (University of Tennessee) – Database dei primi più grandi conosciuti.

9. Errori Comuni e Best Practice

Quando si implementano algoritmi per numeri primi:

1. Evita overflow: Usa aritmetica modulare per numeri grandi.
2. Ottimizza i loop: Nel trial division, testa solo divisori dispari dopo 2.
3. Valida gli input: Gestisci casi edge (n ≤ 1, n pari).
4. Scegli l’algoritmo giusto:
   • n < 10⁶: Sieve of Eratosthenes.
   • 10⁶ < n < 10¹⁸: Miller-Rabin.
   • n > 10¹⁸: ECPP o AKS.

10. Esempio Pratico: Implementazione in Python

Di seguito un esempio di implementazione del test di Miller-Rabin:

def is_prime(n, k=5):
    if n <= 1: return False
    elif n <= 3: return True
    elif n % 2 == 0: return False

    # Scrivi n-1 come d*2^s
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1

    # Test k volte
    for _ in range(k):
        a = random.randint(2, n - 2)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for __ in range(s - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

11. Domande Frequenti

Q: Qual è il numero primo più grande conosciuto?

A gennaio 2023, il primo più grande è 2^82,589,933 − 1, un numero di Mersenne con 24,862,048 cifre, scoperto nel 2018 (fonte).

Q: Perché i numeri primi sono importanti in crittografia?

La sicurezza di RSA si basa sulla difficoltà di fattorizzare il prodotto di due primi grandi (es. 1024-bit). Anche con i computer quantistici (algoritmo di Shor), la crittografia post-quantistica si affida a problemi matematici legati ai primi.

Q: Esiste una formula per generare numeri primi?

No. Nonostante tentativi come il polinomio di Euler (n² + n + 41), non esiste una formula non-triviale che generi solo primi. La distribuzione dei primi è ancora oggetto di ricerca (ipotesi di Riemann).