Alice, Bob e Eva — PRIMES is in P

“Quello che abbiamo detto sul test di primalità di Fermat non è del tutto esatto. Esistono altri test che si comportano nel modo che ti ho descritto, ma per quello specifico test c'è un problema”.

“Quale?”.

“L'esistenza dei numeri di Carmichael”.

“Cosa sono?”.

“Sono numeri composti per i quali il test di Fermat risulta sempre 1”.

“Ahia”.

“Eh, sì. Se non ci fossero loro, il test di Fermat funzionerebbe come ti ho descritto, potresti fare i conti con le probabilità e raggiungere il grado di confidenza richiesto. Ma se incappi in un numero di Carmichael, non ti accorgeresti mai che è composto”.

“Ma sono così frequenti, questi numeri?”.

“No, per fortuna no, sono pochi. Il più piccolo è 561, ce ne sono solo 8220777 compresi tra 1 e 10²⁰, circa uno ogni diecimila miliardi di numeri”.

“Ok, sono pochi, però già prima pensavo che un test probabilistico fosse poco serio, per un Vero Matematico, poi adesso mi dici che ci sono dei numeri che non vengono scoperti: non mi piace”.

“Sì, è vero, ma esistono altri test probabilistici che non hanno questi problemi e sono più sicuri ancora. Il fatto è che fino al 2002 non si conosceva nessun metodo veloce per scoprire in modo deterministico, cioè con certezza, se un numero è primo oppure no”.

“Ehi, il 2002 non è tanto tempo fa. Che è successo?”.

“Il 6 agosto 2002 tre matematici indiani, Manindra Agrawal, Neeraj Kayal e Nitin Saxena hanno pubblicato un articolo sulla rivista Annals of Mathematics dal titolo drastico: PRIMES is in P”.

“Cosa significa?”.

“Nell'intoduzione al loro lavoro, gli autori fanno una storia dei test di primalità, partendo proprio dal nostro test di Fermat e mostrando l'evoluzione dei vari algoritmi. Ti leggo una frase che rappresenta la conclusione della ricerca e risponde alla tua domanda:”.

The ultimate goal of this line of research has been, of course, to obtain an unconditional deterministic polynomial-time algorithm for primality testing. Despite the impressive progress made so far, this goal has remained elusive. In this paper, we achieve this.

“Wow. Quindi hanno trovato un algoritmo polinomiale?”.

“Sì, e il problema dei test probabilistici è stato finalmente risolto. È questo il significato del titolo PRIMES is in P: P è la classe dei problemi polinomiali”.

“Oh, bene”.

“Il problema della fattorizzazione, invece, rimane: non si riesce a fattorizzare un numero in tempi decenti, ma di questo ne avevamo già parlato. È un problema relativo a uno dei problemi del millennio”.

“Sì, ricordo”.

“In questo campo ci sono stati notevoli passi avanti, ma tutti gli algoritmi di fattorizzazione sono lenti, cioè non sono polinomiali. Ma per ora va bene così”.

“Perché?”.

“Diciamo che sarebbe bello scoprire un metodo veloce per fattorizzare un numero. Il giorno in cui dovesse esserci l'annuncio sarebbe certamente un momento storico, anche perché dovrebbero cambiare molte delle nostre abitudini?”.

“In che senso?”.

“Nel senso che tutta la crittografia moderna si basa sulla non esistenza di un metodo veloce per fattorizzare un numero. Se quel metodo viene scoperto, dobbiamo fare a meno della crittografia”.

“Bah, non sarà questa gran cosa. Chi la usa?”.

“Tu, per esempio, tutte le volte che entri in gmail per leggere la tua posta”.

“Eh?”.

“Sì, sì, tutte le volte che entri in un sito sicuro, che fai acquisti su internet, che inserisci qualche password (a meno che tu non faccia girare le password in chiaro, ma non ti conviene molto)”.

⇐ · ⇒