martedì 27 aprile 2010

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 1020, 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)”.

·

7 commenti:

.mau. ha detto...

i numeri di Carmichael sono quelli delle note di Georgia on My Mind, lo sanno tutti!

Knulp ha detto...

bellissima serie di post, complimenti!

Domandina: con quasi-polinomiale ti riferivi a "pseudo-polinomiale"?
(il secondo si riferisce agli algoritmi che sono polinomiali quando l'input è espresso in notazione "unaria"!
In effetti, sono un tipo di algoritmi NP abbastanza attacabile)

zar ha detto...

@.mau., sicuramente lo sanno tutti, io per esempio ho dovuto usare wikipedia per capirlo :-)

@Knulp, francamente non lo so. Se hai delle correzioni da farmi sul linguaggio usato, fai pure. Wikipedia dice che il general number field sieve (http://en.wikipedia.org/wiki/General_number_field_sieve) è super polynomial, mentre in un'altra pagina (http://en.wikipedia.org/wiki/Super-polynomial_time#Sub-exponential_time) parla di sub exponential (per la quale categoria ci sono ben due definizioni).

Knulp ha detto...

purtroppo non sono un esperto di complessità. Stasera guardo con attenzione i link che mi hai passato per vedere se la loro definizione assomiglia alla mia!

Anonimo ha detto...

Le sarebbe piaciuto rimanere con marett. questa mattina, vero??

Knulp ha detto...

Ciao mi sono ripassato un po' di teoria della complessità, e le conclusioni sono:

- pseudo-polinomiale: quando il tempo è una funzione polinomiale del "valore" degli input (e non della loro quantità). In questo caso, poiché i numeri vengono espressi in notazione posizionale (binaria o decimale), la loro "lunghezza" sarebbe esponenziale. Ad esempio, il numero 256 richiede 3 cifre in decimale, ma ha "lunghezza" 256 se indica ad esempio un numero di chicchi di riso. La relazione tra rappresentazione posizionale e quantità è "esponenziale" , quindi gli algoritmi pseudo-polinomiali sono a tutti gli effetti esponenziali nell'input.

- quasi-polinomiali: sono più lenti di qualunque algoritmo polinomiale, ma meno lenti di qualunque algoritmo esponenziale. Praticamente, si tratta di funzioni che non sono dominati dai polinomi, e non dominano gli esponenziali.

Non sono stato chiaro? Scusate, ma è che in effetti l'argomento è complicato...

zar ha detto...

@anonimo: già...

@Knulp: eh, il quasi polinomiale è chiaro, lo pseudo un po' meno, in effetti.