Util Monster
Gratis
Test di primalità · Fattorizzazione · Generazione di primi
Un numero primo è un numero naturale maggiore di 1 che non ha divisori positivi diversi da 1 e da se stesso. Esempi: 2, 3, 5, 7, 11, 13... Tutti i primi tranne 2 sono dispari. I numeri primi sono gli "atomi dei numeri".
Un antico algoritmo sviluppato dal matematico greco Eratostene intorno al 240 a.C. Trova in modo efficiente tutti i numeri primi fino a n segnando iterativamente i multipli di ogni numero primo come composti.
I numeri primi gemelli sono coppie di primi che differiscono di 2: (3,5), (5,7), (11,13), (17,19)... Se esistano infiniti numeri primi gemelli resta un problema irrisolto.
• Crittografia RSA: sicurezza basata sulla difficoltà di fattorizzare numeri grandi • Funzioni hash: tabelle hash di dimensione prima riducono le collisioni • Generazione di numeri casuali: numeri primi negli algoritmi PRNG • Natura: i cicli di vita delle cicale usano numeri primi
Un numero primo è un numero naturale maggiore di 1 che non ha divisori eccetto 1 e se stesso. Il più piccolo numero primo è 2, l'unico primo pari. Sequenza: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29... Il matematico greco Euclide dimostrò intorno al 300 a.C. che esistono infiniti numeri primi. I numeri primi sono chiamati "atomi dei numeri" perché ogni intero > 1 si fattorizza in modo univoco in primi (teorema fondamentale dell'aritmetica). Esempi: 60 = 2² × 3 × 5, 360 = 2³ × 3² × 5.
Il metodo più semplice verifica la divisibilità per tutti i numeri da 2 a n-1, ma è inefficiente. Un miglioramento controlla solo da 2 a √n, poiché se n = a × b, allora a ≤ √n o b ≤ √n. Per 101: √101 ≈ 10.05, quindi basta testare 2, 3, 5, 7. Il test probabilistico di Miller-Rabin gestisce in modo efficiente numeri molto grandi. AKS (2002) è il primo algoritmo deterministico in tempo polinomiale. La crittografia moderna usa numeri di centinaia di cifre, quindi servono test efficienti.
Sviluppato dal matematico greco Eratostene intorno al 240 a.C. Processo: ① Elenca i numeri da 2 a n. ② Segna 2 come primo, elimina i multipli (4,6,8,10...). ③ Il numero successivo non marcato, 3, è primo, elimina i suoi multipli. ④ Continua con 5, 7, ecc. fino a √n. ⑤ I numeri rimanenti sono primi. Per n=30: i primi sono 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Complessità temporale: O(n log log n). Può trovare tutti i primi sotto 1 milione in pochi secondi.
La fattorizzazione in primi esprime un numero come prodotto di primi. In base al teorema fondamentale, ogni intero > 1 ha una fattorizzazione unica. Metodo: ① Parti dal più piccolo numero primo, 2. ② Dividi ripetutamente per 2 finché non è più divisibile. ③ Prova i primi successivi 3, 5, 7... ④ Continua finché il quoziente è 1. Esempio 360: 360÷2=180, 180÷2=90, 90÷2=45, 45÷3=15, 15÷3=5, 5÷5=1. Risultato: 360 = 2³×3²×5. Applicazioni: calcolo di MCD/mcm, semplificazione delle frazioni, sicurezza RSA.
I numeri primi gemelli differiscono di 2: (3,5), (5,7), (11,13), (17,19), (29,31)... La congettura dei primi gemelli afferma che ne esistono infiniti, ma resta non dimostrata. Nel 2013, Yitang Zhang dimostrò che infinite coppie di primi differiscono di ≤70 million, poi ridotti a 246. La congettura di Goldbach (1742): ogni numero pari > 2 è somma di due primi. Esempi: 4=2+2, 6=3+3, 8=3+5, 10=5+5. Verificata fino a 4×10¹⁸ ma ancora non dimostrata.
La crittografia RSA, al centro della sicurezza di Internet, si basa su una moltiplicazione facile ma una fattorizzazione difficile di grandi primi. Generazione delle chiavi: ① Scegli grandi primi p, q (1024+ bit ciascuno). ② Calcola n = p×q (pubblico). ③ Calcola φ(n) = (p-1)(q-1). ④ Scegli l'esponente pubblico e coprimo con φ(n) (di solito 65537). ⑤ Calcola l'esponente privato d tale che e×d ≡ 1 (mod φ(n)). Chiave pubblica: (n,e), chiave privata: (n,d). Cifra: C = M^e mod n, Decifra: M = C^d mod n. Fattorizzare n per trovare p,q romperebbe la crittografia, ma fattorizzare numeri di centinaia di cifre richiede milioni di anni. Altre applicazioni: dimensioni delle tabelle hash prime riducono le collisioni, i cicli di 13/17 anni delle cicale evitano la sovrapposizione con i predatori, ritmi primi nella musica.