Numero primo

Da Wikipedia, l'enciclopedia libera.

La pagina di discussione contiene dei suggerimenti per migliorare la voce: Numero primo

L'insieme dei numeri primi è un sottoinsieme dei numeri naturali. Un numero primo, in matematica, è un numero naturale divisibile unicamente per se stesso e per uno, e diverso da uno. Detto in altro modo, deve avere esattamente due divisori interi 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).

Indice

1 Uno e zero non sono primi
2 Infinità dei numeri primi
3 Scomposizione in fattori primi
4 Applicazioni
5 Problemi aperti
6 Test di primalità
7 Algoritmo in Java per la generazione di numeri primi
8 Algoritmo in C per la generazione di numeri primi
9 Principali teoremi e congetture sui numeri primi
10 Numeri primi inferiori a 500
11 Generalizzazioni
12 Voci correlate
13 Collegamenti esterni

[modifica] Uno e zero non sono primi

Il numero 1 non è un primo poiché ha un solo divisore. Il numero 0 non è primo perché ne ha infiniti. L'unico numero primo pari è 2.

La scelta di non includere 1 tra i numeri primi è dovuta a vari motivi: tra questi, c'è il fatto che una tale inclusione costringerebbe a riformulare in modo più complicato diversi teoremi di matematica, come ad esempio il teorema fondamentale dell'aritmetica e il crivello di Eratostene.

[modifica] Infinità dei numeri primi

Per approfondire, vedi la voce Teorema dell'infinità dei numeri primi.

I numeri primi sono infiniti. La più antica dimostrazione pervenutaci è quella di Euclide, La proposizione 20 del Libro IX degli Elementi afferma infatti che I numeri primi sono più di una qualsiasi assegnata moltitudine di numeri primi. La sua dimostrazione parte da un qualunque insieme di numeri primi $p 1, p 2,..., p n$ , e costruisce un numero primo diverso da tutti i $p i$ . Si inizia moltiplicando tra di loro tutti questi numeri e sommando un'unità, ottendo come risultato un nuovo numero q che potrà essere o non essere primo. Se q è primo, la dimostrazione è terminata; altrimenti esso dovrà avere almeno un divisore d primo. Per costruzione, però, d non può essere nessuno dei $p i$ ; infatti la divisione $q / p i$ dà sempre 1 come resto, quindi, per ogni $i$ , $p i$ non divide $q$ , e quindi $p i$ non divide neanche il suo divisore d. Pertanto, d è l'ulteriore numero primo cercato.

Ecco alcuni esempi numerici. Partendo da 2 e 3, otteniamo $(2\times 3)+1 = 7$ che è un numero primo; aggiungendolo agli altri arriviamo a $(2\times 3 \times 7)+1 = 43$ che è ancora primo; invece $(2\times 3\times7 \times 43)+1 = 1807$ che non è primo ma ha il fattore primo 13.

[modifica] Scomposizione in fattori primi

Per approfondire, vedi la voce Teorema fondamentale dell'aritmetica.

L'importanza dei numeri primi in matematica è enorme e deriva essenzialmente dal teorema fondamentale dell'aritmetica, il cui enunciato è:

qualsiasi numero può essere scomposto in fattori primi, e tale scomposizione è unica.

Ad esempio,

$23244 = 2^2 \times 3 \times 13 \times 149$

e ogni altra fattorizzazione di 23244 in numeri primi è ottenuta da questa permutando i fattori.

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".

[modifica] Applicazioni

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: nell'RSA, uno dei pricipali algoritmi di crittografia asimmetrica, la decrittazione del messaggio richiede la fattorizzazione di un numero di grandi dimensioni, problema che ad oggi rientra ancora nella categoria dei problemi complessi.

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.

[modifica] Problemi aperti

Molte congetture riguardanti i numeri primi sono ancora aperte. Tra queste, la congettura di Goldbach asserisce che ogni numero intero pari maggiore di due è somma di due numeri primi.

La Congettura di Riemann, uno dei problemi insoluti più importanti di tutta la matematica, riguarda la frequenza dei numeri primi ed è stato scelto fra i sei problemi per il millennio nel 2000.

[modifica] Test 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 alla 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 (l o g (N) 12)$ , che si riduce a $O (l o g (N) 6)$ se vale la congettura di Sophie Germaine. Dal 2002 l'algoritmo è stato migliorato di 2 milioni di volte in passi successivi. 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.

[modifica] Algoritmo in Java per la generazione di numeri primi

Questo metodo scritto in linguaggio Java consente la stampa in output tutti i numeri primi inferiori al parametro "limitazione".

questo si basa su un ciclo che scorre tutti i numeri inferiori al parametro e valuta tramite un secondo metodo di nome "primo" se ogni singolo numero è primo o meno.

   public void stampaNumeriPrimi(int limitazione){
       //il numero "limitazione" è il numero a cui tutti i numeri primi stampati
       //sono inferiori
       /**La variabile plot viene utilizzata per scorrere tutti i numeri
        *inferiori a "limitazione"
        */
       int plot=2;
       while(plot<=limitazione){
           if(primo(plot))
               System.out.println(plot);
           plot++;
       }
   }
   /**
    *Questo metodo ci consente di capire se il parametro "numero"
    *è un numero primo, rendendoci una condizione vera o falsa
    */
   protected boolean primo(int numero){
       //istanziamo una variabile di scorrimento
       int plot=numero/2+1;
       //inizializziamo un ciclo che continua finchè la variablie di scrrimento è maggiore di 1
       while(plot>1){
           //se il resto tra la divisione tra il numero preso in considerazione
           //e la variabile di scorrimento è uguale a zero, ritornìamo una condizione falsa
           if(numero%plot==0&&
                   plot!=numero&&
                   plot!=1){
               return false;
           }
           //decrementiamo la variablie di scorrimento di 1
           plot--;
       }
       //se siamo giunti a questo punto, ovvero il numero non è risultato divisibile 
       //per nessun numero inferiore a se stesso, rendiamo nua condizione vera 
       return true;
   }

[modifica] Algoritmo in C per la generazione di numeri primi

Di seguito un algoritmo "base" per la stampa dei numeri primi consecutivi. Una possibile ottimizzazione sarebbe creare una lista dei primi trovati, ed utilizzarli per la divisione dei numeri successivi, invece di utilizzare tutti i dispari. Questo in quanto è inutile provare a dividere per 15, se si è gia provato 3 e 5.

#include <stdio.h>
#include <stdlib.h> 
#include <math.h>

int main(void)
{
       long int dividendo;
       long int divisore;
       long int radice;
       int fermati;     /* segnala la fine del ciclo */
       int conto = 2;   /* contatore */
       
       printf("\n\t**************************");
       printf("\n\n\nPremere invio per iniziare");
       getchar();
       
       /* 2 e' un numero primo, stampa 2 */
       printf("\n%do\t\t%d", 1, 2);
       dividendo = 3;
       
       do
       {
               divisore = 3;
               radice   = sqrt(dividendo );
               fermati  = 0;
               
               do
               {                        
                       /* se il resto (modulo) di dividendo/divisore non è zero */
                       if((dividendo % divisore) != 0)
                       {
                               /* e il divisore è maggiore della radice del dividendo  */
                               if (divisore > radice)
                               {
                                       /* allora il dividendo è primo, e lo stampa */
                                       printf("\n%do\t\t%d", conto, dividendo);
                                       ++conto;
                                       fermati = 1;
                               }
                       }
                       else {
                               fermati = 1;
                       }
                       divisore += 2; /* passa al numero dispari successivo */
               }
               while (fermati == 0);
               
               dividendo += 2;
       }
       while(dividendo);
       
       getchar();
}

[modifica] Principali teoremi e congetture sui numeri primi

Congettura di Goldbach
Congettura di Opperman
Congettura del numero di classe
Congettura dei numeri primi gemelli
Teorema di Shimura-Taniyama (dimostrato 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
Postulato di Bertrand (dimostrato nel 1850 da Cebicev)
Teorema di Mills
Teorema di Wilson
Test di Lucas - Lehmer

[modifica] 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.

[modifica] Generalizzazioni

Per approfondire, vedi la voce dominio d'integrità.

La definizione di numero primo può essere estesa a qualunque anello commutativo; vi sono generalmente due modi di estendere la definizione, non equivalenti fra loro in generale:

un elemento è irriducibile se è un elemento non unitario che non può essere scritto come il prodotto di due elementi non unitari (definizione corrispondente a quella data sopra);
un elemento è primo se ogni volta che divide il prodotto $a b$ , allora divide $a$ oppure $b$ (ad esempio: 5 divide $45 = 15 \times 3$ e divide 15; 4, che non è primo, divide $84 = 14 \times 6$ , ma non divide né 14 né 6).