In matematica, un numero primo è un
numero naturale maggiore di 1 che sia
divisibile solamente per 1 e per sé stesso;
al contrario, un numero maggiore di 1 che
abbia più di due divisori è detto composto.
Ad esempio, 2, 3 e 5 sono primi, mentre 4 e
6 non lo sono perché sono divisibili
rispettivamente anche per 2 e per 2 e 3.
L'unico numero pari primo è 2, in quanto
tutti gli altri sono divisibili per 2.
La successione dei numeri primi inizia con
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 ...
Quello di numero primo è uno dei concetti
basilari della teoria dei numeri, la parte
della matematica che studia i numeri
interi: alla base di questa concetto vi è la
possibilità di costruire con essi,
attraverso la moltiplicazione, tutti gli
altri numeri interi, nonché l'unicità di
tale fattorizzazione. I primi sono inoltre
infiniti e la loro distribuzione è stata
oggetto di molte ricerche.
Sono rilevanti anche in molti
altri ambiti della matematica
pura, come ad esempio
l'algebra o la geometria;
recentemente hanno assunto
un'importanza cruciale anche
nella matematica applicata, e
in particolare nella
crittografia.
Esistono inoltre i
numeri primi gemelli ,
numeri primi che
differiscono tra loro di
due unità . Fatta
eccezione per la coppia (2,
3), questa è la più piccola
differenza possibile fra
due primi. Alcuni esempi
di coppie di primi gemelli
sono 5 e 7, 11 e 13, e 821
e 823.
Eratostene di Cyrene (in greco:
Έρατοσθένης, Eratosthenes;
Cirene, 276 a.C. – Alessandria
d'Egitto, 194 a.C.) è stato un
matematico, astronomo,
geografo e poeta greco antico.
Fu uno degli intellettuali più
versatili della sua epoca. Terzo
bibliotecario della Biblioteca di
Alessandria e precettore di
Tolemeo IV Filopatore, è oggi
ricordato soprattutto per aver
misurato per primo con grande
precisione le dimensioni della
Terra.
Tra i risultati matematici di
Eratostene, quello più noto è il
crivello di Eratostene, un metodo
per individuare i numeri primi.
Il crivello di Eratostene è un antico procedimento per il
calcolo delle tabelle di numeri primi fino ad un certo numero n
prefissato. Deve il nome al matematico Eratostene di Cirene,
che ne fu l'ideatore. È a tutt'oggi utilizzato come algoritmo di
calcolo dei numeri primi da molti programmi per computer;
pur non essendo un algoritmo straordinariamente efficiente,
infatti, è in compenso piuttosto semplice da tradurre in un
qualsiasi linguaggio di programmazione.
Il procedimento è il seguente: si scrivono tutti i naturali a
partire da 2 fino n in un elenco detto setaccio (in
programmazione spesso l'elenco è implementato da un array).
Poi si cancellano (setacciano) tutti i multipli del primo numero
del setaccio (escluso lui stesso). Si prosegue così fino ad
arrivare in fondo. I numeri che restano sono i numeri primi
minori od uguali a n.
È come se si utilizzassero dei
setacci a maglie via via più
larghe: il primo lascia passare
solo i numeri non multipli di 2,
il secondo solo i non multipli di
3, e così via.
Nel caso n = 50, ad esempio, il
procedimento di setacciatura si
conclude con il numero 7 perché
7 è il massimo primo il cui
quadrato non supera 50 e si può
provare che il procedimento di
setacciatura per ricercare i
primi fino ad un certo numero n
cessa sempre quando si supera
la radice quadrata di n. Infatti
ogni numero a del setaccio
iniziale, contenente tutti i
numeri naturali non superiori
ad un dato n, cade dal setaccio
che corrisponde al più piccolo
dei suoi divisori primi.
La parola crittografia deriva
dall'unione di due parole
greche: κρυπτὁς (kryptós) che
significa "nascosto", e γραφία
(graphía) che significa
"scrittura". La crittografia
tratta delle "scritture
nascoste", ovvero dei metodi
per rendere un messaggio
"offuscato" in modo da non
essere comprensibile a persone
non autorizzate a leggerlo. Un
tale messaggio si chiama
comunemente crittogramma.
Lo studio della crittografia e
della crittanalisi si chiama
comunemente crittologia.
La vera novità del secolo scorso è l'invenzione di una tecnica crittografica che utilizza
chiavi diverse per cifrare e per decifrare un messaggio, facilitando incredibilmente il
compito di distribuzione delle chiavi. Infatti in questo caso non è necessario
nascondere le chiavi o le password: c'è una chiave per crittografare, che chiunque può
vedere, e una per decifrare, che conosce solo il destinatario senza necessità quindi di
riceverla (scambiarla) dal mittente. In altre parole, se A vuole ricevere un messaggio
segreto da B, manda a B una scatola vuota con un lucchetto aperto senza chiavi. B
mette dentro il messaggio, chiude il lucchetto, e rimanda il tutto ad A, che è l'unico
ad avere le chiavi. Chiunque può vedere passare la scatola, ma non gli serve a niente.
A non deve correre rischi con le sue chiavi.
Nel 1976 sono stati due esperti, Whitfield Diffle e Martin E.Hellman, della Stanford
University, a introdurre l'utilizzo della chiave pubblica per la crittazione e
l'autenticazione; nell'anno seguente il gruppo di ricerca del MIT formato da Ronald
L. Rivest, Adi Shamir e Loenard M. Adleman realizza il primo sistema a chiave
pubblica, in questo modo viene ideato l'algoritmo RSA.
Il funzionamento di questo sistema è basato sul fatto che è matematicamente molto
facile moltiplicare due numeri primi (che singolarmente rappresentano la chiave
privata, quella che solo A conosce per decifrare), ma è invece molto difficile il
problema inverso ovvero risalire ai fattori primi del numero ottenuto dal precedente
prodotto (che invece rappresenta la chiave pubblica che chiunque può vedere e che si
usa per crittografare).
Siccome la crittografia asimmetrica è molto lenta se si devono spedire grandi
quantità di dati, spesso si usa questo tipo di crittografia per scambiarsi una chiave
con cui iniziare una comunicazione in crittografia simmetrica, molto più semplice,
veloce e sicura.