Numero primo
L'insieme dei numeri primi è un sottoinsieme dei numeri naturali. Un numero primo, in matematica, è un numero naturale divisibile unicamente per sé stesso e per l'unità e diverso, per convenzione, dall'unità. Detto in altro modo, deve avere esattamente due fattori distinti.
I primi numeri primi sono: 2, 3, 5, 7, 11, 13, 17...
(4 è divisibile per 2, 6 è divisibile per 3, 8 è divisibile per 2, 9 è divisibile per 3, 10 è divisibile per 2, e così via)
I numeri primi sono infiniti. La più antica dimostrazione pervenutaci è quella di Euclide: egli mostrò come, partendo da una serie finita di primi se ne possano sempre trovare degli altri. La serie è costituita dai numeri primi p1,p2,...,pn che moltiplicati tra loro, ed aggiungendovi un'unità danno come risultato un nuovo numero q che potrà essere o non essere primo: se esso è primo allora l'algoritmo ha funzionato. Se q non dovesse essere primo, però dovrà essere divisibile per un altro primo, che non potrà essere uno dei pn in quanto essi porterebbero ad una divisione con resto 1.
La formula risulta: q = (p1 * p2 * ... * pn) + 1; quindi, per esempio: 7 = (2 * 3) + 1.
La loro importanza in matematica è enorme e deriva dal teorema fondamentale dell'aritmetica, il cui enunciato è: qualsiasi numero può essere scomposto in fattori primi, e tale scomposizione è unica. Questa è tra l'altro la ragione per cui convenzionalmente si esclude 1 dall'insieme dei numeri primi: l'unicità della scomposizione in fattori viene considerata sufficientemente importante da prevalere sulla definizione "ingenua".
Per certe classi di proprietà, come ad esempio le funzioni additive e le funzioni moltiplicative, è sufficiente dimostrare che siano valide per i numeri primi, o per le potenze dei numeri primi, affinché valgano per tutti i numeri naturali.
Praticamente tutti i grandi matematici si sono occupati, prima o poi, di numeri primi; recentemente i numeri primi (assieme alla branca della matematica che li studia, la teoria dei numeri) hanno trovato applicazione nel campo della crittologia.
Il più importante problema ancora insoluto di tutta la matematica (uno dei problemi del millennio) è la congettura di Riemann sulla frequenza dei numeri primi: l'Istituto Clay di matematica ha messo in palio un milione di dollari per chiunque saprà dimostrarne la verità o la falsità.
I numeri primi sono comunque sempre apparsi, in modo spesso inaspettato, nelle scienze più disparate: hanno una loro importanza perfino in entomologia, dove si è notato che alcune specie di insetti che hanno un periodo larvale di parecchi anni tendono ad averlo pari a un numero primo (11, 13 e 17 sono i più conosciuti) per evitare che i loro predatori, che hanno in genere cicli biennali o triennali di popolazione, si trovino "in fase" sempre nel momento di massima loro espansione e quindi rendano più precaria la sopravvivenza della specie.
| Indice |
Verifica di primalità
Esistono vari metodi per generare, controllare o certificare la primalità di un numero. Il più antico è sicuramente il crivello di Eratostene, noto già in epoca classica, ma computazionalmente molto costoso. È d'altra parte vero che la scomposizione in fattori primi di un numero non è un'operazione veloce, e proprio questa sua caratteristica viene sfruttata per la creazione di codici cifrati. Più rapido è verificare se un numero è primo o no, anche se i test di primalità più efficienti utilizzati (test con curve ellittiche ECPP) sono statistici e non danno una certezza assoluta: tuttavia l'errore dei test può essere reso piccolo a piacere. Nel 1992 Adleman e Huang, modificando l'algoritmo di Goldwasser - Kilian, mostrarono come la verifica di primalità (solitamente detta PRIMES, in inglese) appartenga nella classe RP. Dato che nel 1977 Solovay e Strassen avevano mostrato che la verifica appartiene anche alla classe co-RP, il test di Adleman e Huang mostrò che PRIMES appartiene alla classe ZPP, intersezione di RP e co-RP. Nel 2002 Agrawal, Kayal e Saxena fornirono un algoritmo deterministico polinomiale per PRIMES, noto come algoritmo AKS, di complessità O(log(N)12), che si riduce a O(log(N)6) se vale la congettura di Sophie Germaine. Dal 2002 l'algoritmo è stato migliorato di 2 milioni di volte in passi succesivi. Comunque, per ora, questo algoritmo non comporta significativi vantaggi rispetto ai ben noti metodi statistici, né implica alcunché sulla fattorizzazione di un numero (se non nel test di verifica di primalità), e quindi nella crittografia basata sui primi. Tuttavia le ricerche a riguardo sono appena all'inizio, e non è detta l'ultima parola.
Gruppi e numeri primi
Principali teoremi e congetture sui numeri primi
- Congettura di Goldbach
- Congettura di Opperman
- Congettura del numero di classe
- Congettura dei numeri primi gemelli
- Congettura di Shimura-Taniyama (dimostrata parzialmente da Andrew Wiles e integralmente da Brian Conrad, Fred Diamond, Richard Taylor e Christoph Breuil nel 2005)
- Ipotesi di Riemann
- Legge di reciprocità quadratica (Teorema dei numeri primi di Gauss)
- Numero primo di Mersenne
- Piccolo teorema di Fermat
- Teorema dei numeri primi
- Teorema dell'infinità dei numeri primi
- Teorema di Bertrand
- Teorema di Mills
- Teorema di Wilson
- Test di Lucas-Lehmer
Numeri primi inferiori a 500
2; 3; 5; 7; 11; 13; 17; 19; 23; 29; 31; 37; 41; 43; 47; 53; 59; 61; 67; 71; 73; 79; 83; 89; 97; 101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 157; 163; 167; 173; 179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 239; 241; 251; 257; 263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 331; 337; 347; 349; 353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 421; 431; 433; 439; 443; 449; 457; 461; 463; 467; 479; 487; 491; 499;
Voci correlate
Collegamenti esterni
- Algoritmo AKS
- Verifica di primalità secondo AKS
- The Prime Pages
- Istituto Clay di matematica - premio per la congettura di Riemann
Categoria:Teoria dei numeri
tokipona:nanpa_lawa
zh-cn:素数