Numeri primi: i mattoni dell'aritmetica

Un numero primo è un intero > 1 divisibile solo per 1 e per sé stesso. I primi 20 numeri primi: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71.

I numeri non primi (maggiori di 1) si chiamano composti. Sono prodotto di primi più piccoli.

Il numero 1 non è primo né composto per convenzione matematica (questione di coerenza nel teorema fondamentale).

Teorema fondamentale dell'aritmetica

Ogni intero > 1 si esprime in modo unico (a meno dell'ordine) come prodotto di numeri primi. Dimostrato da Euclide (~300 a.C.) negli Elementi.

n = p₁^a₁ × p₂^a₂ × ... × p_k^a_k

Esempi:

• 12 = 2² × 3
• 60 = 2² × 3 × 5
• 360 = 2³ × 3² × 5
• 1000 = 2³ × 5³
• 1001 = 7 × 11 × 13 (storicamente significativo)

Crivello di Eratostene

Algoritmo antico (Eratostene di Cirene, ~240 a.C.) per trovare tutti i primi fino a n:

1. Scrivi tutti i numeri da 2 a n
2. Il più piccolo non cancellato è primo: cancella tutti i suoi multipli
3. Ripeti con il prossimo primo
4. Fermati quando il primo supera √n

Complessità: O(n log log n), molto efficiente per n < 10⁸.

Test di primalità

1. Trial division

Verifica se n è divisibile per qualche primo p ≤ √n. O(√n). Usa fino a circa 10⁹.

2. Test di Miller-Rabin

Probabilistico: verifica primalità con probabilità di errore < 1/4^k per k ripetizioni. Deterministico con specifiche basi fino a 3,3 × 10¹⁴ (Miller 1976, Rabin 1980).

3. AKS primality test

Agrawal, Kayal, Saxena (2002): primo algoritmo deterministico polinomiale per primalità. Storicamente importante, computazionalmente più lento di Miller-Rabin in pratica.

4. ECPP (Elliptic Curve Primality Proving)

Usato per certificare primi gigantesci. Il più grande primo dimostrato primo via ECPP ha ~40.000 cifre.

Teorema dei numeri primi

Dimostrato indipendentemente da Jacques Hadamard e Charles de la Vallée Poussin nel 1896:

π(n) ~ n / ln(n)

dove π(n) è il numero di primi ≤ n. Approssimazione più accurata: π(n) ≈ Li(n) (logaritmo integrale).

Densità primi:

• Fino a 100: 25 primi (25%)
• Fino a 1.000: 168 (16,8%)
• Fino a 10.000: 1.229 (12,3%)
• Fino a 1.000.000: 78.498 (7,85%)
• Fino a 10⁹: 50.847.534 (5,08%)

I primi "diradano" ma non finiscono mai (teorema di Euclide: infiniti primi).

Dimostrazione infinità dei primi (Euclide)

Supponi per assurdo che i primi siano finiti: p₁, p₂, ..., p_n.

Consideriamo N = p₁ · p₂ · ... · p_n + 1.

N non è divisibile per alcun p_i (lascerebbe resto 1).

Quindi N è primo oppure ha un fattore primo non nella lista.

Contraddizione → i primi sono infiniti. QED Euclide ~300 a.C.

Primi famosi

Primi di Mersenne

Della forma M_p = 2^p − 1 con p primo. Il più grande primo conosciuto (fine 2024) è 2^136.279.841 − 1 (51° primo di Mersenne), con ~41 milioni di cifre.

Progetto GIMPS (Great Internet Mersenne Prime Search): computing distribuito volontario.

Primi di Fermat

F_n = 2²ⁿ + 1. Fermat congetturò (1640) che tutti i F_n fossero primi. Eulero (1732) dimostrò F₅ = 4.294.967.297 = 641 × 6.700.417 (composto!). Ad oggi solo F₀..F₄ (3, 5, 17, 257, 65537) sono primi.

Primi gemelli

Coppie (p, p+2) con entrambi primi. Esempi: (3,5), (5,7), (11,13), (17,19), (29,31), ...

Congettura dei primi gemelli (aperto): ci sono infinite coppie. Non dimostrato. Yitang Zhang (2013) dimostrò che infiniti primi sono a distanza < 70.000.000. Dall'allora la bound è stata ridotta a < 246.

Primi di Sophie Germain

p primo tale che 2p + 1 è anche primo. Usati in crittografia. Sophie Germain (1831) li studiò nella dimostrazione parziale dell'Ultimo teorema di Fermat.

Crittografia e numeri primi

La sicurezza dei principali algoritmi crittografici si basa sulla difficoltà della fattorizzazione di grandi semi-primi (prodotto di due primi):

RSA (Rivest-Shamir-Adleman, 1977)

Chiave pubblica e privata basate su due primi p, q di ~300-600 cifre ciascuno. Decifrare senza conoscere p e q richiede fattorizzare n = p·q, computazionalmente infattibile.

RSA-2048 (2048 bit): sicurezza attuale. RSA-4096: sicurezza extra. RSA-1024 ormai rotto nel 2019.

Minaccia quantistica

Algoritmo di Shor (1994) su computer quantistico fattorizza n in tempo polinomiale. RSA cadrà quando computer quantistici con migliaia di qubit saranno realizzati. NIST sta standardizzando crittografia post-quantistica.

Funzioni aritmetiche importanti

Funzione di Eulero φ(n)

Numero di interi da 1 a n coprimi con n.

Formula: φ(n) = n · Π(1 − 1/p) per p primi divisori di n.

Esempi:

• φ(10) = 10 · (1 − 1/2) · (1 − 1/5) = 10 · 0,5 · 0,8 = 4 (gli interi 1, 3, 7, 9 sono coprimi con 10)
• φ(12) = 12 · (1 − 1/2) · (1 − 1/3) = 4 (1, 5, 7, 11)
• φ(p) = p − 1 per p primo

Teorema di Eulero: se gcd(a, n) = 1, allora a^φ(n) ≡ 1 (mod n). Fondamentale in crittografia.

Funzione somma dei divisori σ(n)

Somma di tutti i divisori positivi di n. Per p primo: σ(p) = 1 + p.

σ(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28.

Numeri perfetti

Interi uguali alla somma dei loro divisori propri (escluso se stesso):

• 6 = 1 + 2 + 3
• 28 = 1 + 2 + 4 + 7 + 14
• 496, 8128, 33.550.336, ...

Formula Eulero: un numero pari è perfetto sse è della forma 2^p-1(2^p − 1) con 2^p − 1 primo di Mersenne. Non si sa se esistano numeri perfetti dispari (problema aperto).

Numeri amici

Coppia (a, b) tali che σ(a) − a = b e σ(b) − b = a. Primi esempi: (220, 284), (1184, 1210), (2620, 2924).

Congetture aperte celebri

Congettura di Goldbach (1742)

Ogni pari > 2 è somma di due primi. Verificata fino a ~4 × 10¹⁸, non dimostrata.

Ipotesi di Riemann (1859)

Tutti gli zeri non banali della funzione zeta di Riemann hanno parte reale = 1/2. Implica distribuzione molto precisa dei primi. Premio Millennium: $1 milione.

Congettura dei primi gemelli

Infinite coppie (p, p+2) entrambe prime.

Congettura di Legendre

C'è sempre almeno un primo fra n² e (n+1)².

Il più grande primo conosciuto

A ottobre 2024: 2^136.279.841 − 1

• 41.024.320 cifre
• 51° primo di Mersenne
• Trovato da Luke Durant via GIMPS (progetto volontario GPU-based)
• Tempi di verifica: ~1 mese su CPU moderna

Per contesto: l'universo osservabile contiene ~10⁸² atomi. Un primo con 41 milioni di cifre è inconcepibile.

Fattorizzazione algoritmi avanzati

Pollard's rho

Algoritmo probabilistico O(n^1/4). Efficiente per semi-primi con fattori medio-piccoli.

Quadratic Sieve (QS)

Algoritmo sub-esponenziale, pratico per n fino a ~10¹⁰⁰.

Number Field Sieve (NFS)

Miglior algoritmo classico noto: complessità L(1/3). Rotto RSA-768 nel 2009.

Algoritmo di Shor (quantistico)

Polinomiale O((log n)²·log log n). Romperà RSA quando ci saranno computer quantistici pratici.

Applicazioni moderne

Crittografia

• RSA: e-commerce, SSL/TLS, firme digitali
• Diffie-Hellman: scambio chiavi
• ElGamal: cifratura asimmetrica
• Curve ellittiche (ECC): alternativa più efficiente

Generatori pseudocasuali

Blum Blum Shub: generatore basato su difficoltà di fattorizzazione, crittograficamente sicuro.

Funzioni hash

Alcuni algoritmi usano moduli primi per migliore distribuzione (universal hashing).

Teoria dei codici

Reed-Solomon su GF(pⁿ) per correzione errori in CD, QR code, DVB.

Calcolo distribuito

GIMPS Mersenne search, SETI@home architecture: test primalità volontari globali.

Esempi notevoli

Esempio 1 — Fattorizzazione 360

360 = 2³ × 3² × 5
Divisori: (3+1)(2+1)(1+1) = 24
Lista: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360

Esempio 2 — Numero di Carmichael

561 = 3 × 11 × 17. Composto, ma supera test di Fermat per ogni base coprimeo — "pseudo-primo forte". Scoperto da Korselt 1899, catalogato da Carmichael 1910.

Esempio 3 — Primalità di 1.000.003

√1.000.003 ≈ 1000. Dobbiamo testare divisibilità per primi ≤ 1000. Nessun fattore trovato → 1.000.003 è primo.

Funzioni in Excel / Sheets / Python

Python

from sympy import isprime, primerange, factorint, primepi

isprime(1000003)     # True
list(primerange(1, 50))  # [2, 3, 5, 7, ...]
factorint(360)       # {2: 3, 3: 2, 5: 1}
primepi(10**6)       # 78498 (pi function)

Excel / Sheets

Nessuna funzione nativa per primalità o fattorizzazione. Usa Python/VBA o formula custom con LAMBDA (Excel 365).

Errori comuni

• 1 è primo? No, è un'unità. Né primo né composto per convenzione
• 2 è pari e primo: l'unico
• Fattorizzazione dei negativi: estesa con unità ±1 e primi signed. In ℕ non si applica
• Crittografia con "piccoli primi": RSA con chiavi < 2048 bit è obsoleto

FAQ

Perché 1 non è primo?

Per convenzione che preserva il teorema fondamentale dell'aritmetica: se 1 fosse primo, 6 = 1 × 2 × 3 = 1 × 1 × 2 × 3 avrebbe fattorizzazioni multiple.

Come trovare primi grandi?

Per curiosità: GIMPS volontariato. Per uso crittografico: generazione pseudocasuale + test Miller-Rabin.

Quanti primi ci sono fino a un milione?

π(10⁶) = 78.498. Circa 1 numero su 12-13 è primo nell'intervallo.

Primi gemelli sono infiniti?

Congettura aperta. Prova di Zhang 2013: infinite coppie a distanza < 70 milioni. Ridotto a < 246 con collaborazione Polymath.

RSA è sicuro?

Sì per chiavi ≥ 2048 bit (per ora). Minacce future: computer quantistici. NIST standardizzando crittografia post-quantica.

Come verificare se un numero gigantesco è primo?

Miller-Rabin probabilistic, AKS deterministic, ECPP per certificazioni pubbliche.

Conclusione

I numeri primi sono i mattoni irriducibili dell'aritmetica. Euclide dimostrò la loro infinità 2300 anni fa; oggi alimentano la sicurezza digitale mondiale. Le formule fondamentali — teorema aritmetica, crivello Eratostene, funzione φ — sono evergreen: varranno fra 2000 anni come valgono oggi. La matematica più semplice (contare i fattori) alla base della matematica più profonda (Riemann, quantum).

Aggiornato a luglio 2026