L’indiano serve il primo

Manindra Agrawal, docente di matematica pura all’Istituto Indiano di Tecnologia in Kanpur, era praticamente sconosciuto nei circoli internazionali del matematici di serie A. Per questo motivo è stato ignorato per parecchie settimane quando, nell’agosto 2002, ha annunciato di aver trovato una soluzione teorica a uno dei più annosi e rispettati problemi della matematica moderna, e cioè la scomposizione in numeri primi. Poi Hendrik Lenstra, famoso matematico americano, docente alla università di Berkeley in California, ha riconosciuto per primo il colpo di genio del collega californiamo e ha così convinto i suoi pari a interessarsi del documento che Agrawal ha scritto e cercava di far circolare negli ambienti accademici.
Per capire quale sia la contribuzione del cattedrattico indiano, facciamo un passo indietro. Come si fa a decidere se un numero intero è perfettamente divisibile per undici? Probabilmente ve lo hanno insegnato a scuola e possibilmente non ve lo ricordate più: si tratta, dopotutto, di una tra le tante abilità che ci piovono addosso ma che alla prova dei fatti risultano poco utili e finiamo per accantonare. Capire se un numero è divisibile per cinque, invece, è molto facile: sono divisibili per cinque tutti e soli i numeri che finiscono con uno zero o con un cinque. D’altra parte per capire se un numero è divisibile per sette conviene proprio fare la divisione e vedere cosa salta fuori, non ci sono metodi più semplici.
Manindra Agrawal ha trovato un sistema universale per scoprire se un numero è primo. Anche qui, forse servirà un rapido ripasso delle nozioni della scuola: un numero intero si chiama “numero primo” quando nessun altro numero più piccolo lo sa dividere esattamente, quindi per esempio 121 non è primo (si può dividerlo per 11) ma 97 lo è.
Esistevano già diversi metodi per calcolare se un numero sia primo. Il più vecchio viene addirittura dall’antica Grecia: è il cosiddetto “crivello di Eratostene” e prevede sostanzialmente che si provi a dividere il numero candidato per tutti i numeri più piccoli della sua metà e che sappiamo già essere numeri primi. Ma è un sistema lentissimo e richiede quantità prodigiose di memoria in un calcolatore che venga messo al lavoro. Per questo motivo esiste una specie di “campionato mondiale dei numeri primi”: chi trova un numero primo che sia maggiore del campione precedente assume il titolo di campione e lo tiene sin quando non viene a sua volta spodestato. Il titolare del campionato nel momento in cui scriviamo è un numero della lunghezza di quattro milioni di cifre.
Esistono anche sistemi estremamente veloci ma imprecisi: a volte sbagliano e giudicano che un numero sia primo quando non lo è. Il metodo di Agrawal invece fornisce sempre la risposta esatta. La sua esecuzione su un numero arbitrariamente grande richiede circa due settimane di lavoro a un moderno calcolatore: d’altra parte la prima stesura del programma che usa l’algoritmo di Agrawal è già stata sottoposta all’attenzione di un nugolo di matematici e di informatici alla caccia di ottimizzazioni; il professore indiano spera che i miglioramenti sul software possano portare a una riduzione di questo tempo sino al 90%.
La scoperta di Manindra Agrawal non ha importanza solo per i matematici. Tutte le moderne procedure informatiche di sicurezza si basano in ultima analisi proprio sulla difficoltà nello scoprire se un numero molto grande sia un numero primo. Se il nuovo algoritmo venisse migliorato sino a offrire risposte immediate, immediatamente diventerebbero insicure tutte le transazioni interbancarie, le carte di credito e gli acquisti effettuati su Internet via commercio elettronico; diverrebbero intercettabili tutti i messaggi segreti e leggibili i documenti crittografati; sarebbe banale copiare e sproteggere i DVD e tutti i documenti digitali protetti dall’autore. Hollywood e la CIA, insomma, tremano per le conseguenze del lavoro di un matematico indiano: così va il mondo.