RASSEGNA STAMPA
21 OTTOBRE 2002
RASSEGNA STAMPA | 21 OTTOBRE 2002 |
|
Fondamentali per i sistemi di sicurezza
della Rete e per la moderna crittografia, questi numeri sono difficili da
individuare. Ora due ricercatori hanno
trovato un nuovo algoritmo
Una
delle questioni che hanno da sempre affascinato i matematici è il problema dei
numeri primi. Uno dei primi teoremi che
l'uomo abbia mai dimostrato afferma che i numeri primi sono infiniti. Il teorema è scritto in uno dei libri più
famosi del mondo: gli «Elementi» di Euclide, scritto verso il 300 avanti
Cristo. Altro gran problema è
determinare tutti i numeri primi, trovare cioè un modo per trovare tutti i
numeri primi tramite un algoritmo.
Ricordo che un numero è primo se è divisibile solo per se stesso e per
l'unità. E' un problema molto antico di cui si sono occupati i Cinesi ed i
Gred. Eratostene, circa nel 240 a.C. inventò il più antico algoritmo per
testare i numeri primi. Fermat nel
XVII secolo trovò un altro risultato noto come «Il piccolo Teorema di
Fermat». La storia è continuata sino ai
tempi nostri.
Potrebbe
sembrare il solito problema da matematici il trovare un test che riesca a
determinare se un numero è primo oppure no e se non lo è determinare i fattori
in cui si può spezzare. Per nulla; è
anzi un problema che ha moltissime ripercussioni anche sulla vita di tutti i
giorni. Un esempio: uno dei problemi
principali di coloro che usano la rete, che v'immettono dati anche riservati
(per esempio il numero di una carta di credito) è di essere sicuri di non
correre il rischio che quei dati siano visti da persone che ne possono fare un
uso improprio. Ebbene i sistemi per rendere sicure le comunicazioni in rete
sono basati sui numeri primi, ovvero sui testi di primalità. Nel corso dei secoli si sono avuti dei
risultati che indicavano come testare se un numero era primo oppure no. Ai nostri giorni abbiamo a disposizione
computer molto veloci con cui si possono utilizzare gli algoritmi per la
primalità. Il problema è il tempo che occorre al computer per fare i
conti. Proprio il fatto che il tempo
necessario è assai lungo è la chiave che permette di essere ragionevolmente
sicuri sulla codificazione dei messaggi e sulla sicurezza delle informazioni. E' evidente che se i matematici riescono a
trovare algoritmi che diminuiscono il tempo nel quale si riesce a stabilire se
un numero è primo, diminuisce il tempo di sicurezza per le informazioni
crittate utilizzando i numeri primi.
Insomma
i numeri primi hanno un ruolo fondamentale nella moderna crittografia, il
problema cioè di inviare e ricevere messaggi senza che il «nemico» possa
comprenderli anche se ne riesce a venire in possesso. Nel 1976 viene fondata la RSA Data Security Inc in California. La sigla è composta dalle iniziali dei tre
nomi dei fondatori: Rivest, Shamir e Adleman.
Il loro sistema di cifratura era basato sulla matematica dei numeri
primi. La società è divenuta una delle
più importanti del mondo nel settore.
Il loro sistema è stato utilizzato dal Governo Federale degli USA, dalla
NATO e fa parte del sistema operativo di Microsoft. Chiave del sistema è la
fattorializzazione di un numero in fattori primi. Il numero in questione che è
la chiave del sistema di cifratura, era nel 1996, di 155 cifre. La RSA assegna premi a chi riesce a
fattorizzare numeri grandi. Per 100
cifre lo hanno vinto nel 1988 due matematici: Arjen Lenstra (vincitore di
medaglia Fields) e Mark Manasse. Si è
arrivati ai numeri RSA di 110 cifre nel 1993.
Per saperne di più e tentare di vincere i premi (che sono di migliaia di
dollari) si può andare al sito: www.rsa.com. (Si veda il libro «Mathematical
Mysteries», di Calvin Clawson, Plenum Press, Londra, 1996).
Poche settimane fa tre informatici indiani hanno annunciato di aver trovato un algoritmo di calcolo che permette di stabilire se un numero è primo oppure no in un tempo che è di tipo polinomiale. Soprattutto è un algoritmo di tipo deterministico, mentre gli altri algoritmi utilizzati anche commercialmente per i test (che hanno sempre un tempo polinomiale) sono di tipo probabilistico. Bisogna dire che per gi usi pratici gli algoritmi probabilistici sono molto accurati, tuttavia era un risultato teorico che si attendeva da tempo. L'articolo originale è in rete (www.cse.iitk. ac.in); non è stato ancora pubblicato ma il risultato è stato considerato attendibile dagli esperti. I tre informatici si chiamano Manindra Agrawal, Neeraj Kayal e Nitin Saxena. Lavorano al dipartimento di Informatica ed Ingegneria dell'Indian Institute of Tecnology di Kanpur in India. Se pur questo algoritmo non ha migliorato il tempo necessario per arrivare al risultato, è molto importante perché è una dimostrazione in tutti i casi possibili.