Fattorizzare n è lento, stabilire se n è primo è veloce.
“Un aforisma?”.
“No, è quello che abbiamo sperimentato la volta scorsa. Ci si mette poco tempo per stabilire se un numero è primo oppure no, in tre minuti abbiamo analizzato un numero di 317 cifre. Invece per fattorizzare un numero ci si mette molto tempo, più di un minuto per sole 82 cifre, se ricordi”.
“Ricordo, ricordo. Ma come mai questa differenza?”.
“Eh, finora non è stato scoperto alcun algoritmo veloce per fattorizzare. Cioè, ne conosciamo di molto più veloci rispetto alla tecnica divisioni successive per tutti i numeri primi fino alla radice quadrata del numero, ma sono ugualmente lenti”.
“Si può quantificare in qualche modo, questa velocità?”.
“Sì, si dice che i test di primalità sono polinomiali”.
“Cosa significa?”.
“Che il tempo necessario per completare l'esecuzione del programma è proporzionale a una qualche potenza del numero di cifre di cui è composto il numero da fattorizzare”.
“Qualunque potenza va bene?”.
“Bé, più piccola è la potenza, più veloce è il programma. Il fatto è che gli algoritmi per fattorizzare non sono polinomiali, ma esponenziali, o quasi esponenziali (non chiedermi la definizione di quasi esponenziale perché non c'è accordo nemmeno tra gli informatici, comunque sono molti più lenti rispetto agli altri)”.
“Ok, ma perché?”.
“Questo è uno dei problemi aperti della matematica, uno dei cosiddetti problemi del millennio”.
“Quelli da un milione di dollari?”.
“Precisamente. In questo caso la questione è la seguente: esistono problemi per i quali è molto facile verificare una soluzione, se la si possiede, ma che sono praticamente impossibili da risolvere direttamente? Sembra proprio che il problema della fattorizzazione di un numero appartenga a questa categoria: è molto facile moltiplicare due fattori, ma è molto difficile scomporre un numero”.
“Sembra?”.
“Sì, stiamo parlando di un problema aperto, detto P vs NP. Tra l'altro, se si riesce a trovare un algoritmo polinomiale (quindi veloce) che risolve uno solo dei problemi della categoria NP (quella dei problemi difficili da risolvere), allora è stato dimostrato che tutti i problemi di quella categoria possono essere risolti in tempo polinomiale. E la sicurezza della crittografia moderna non esisterebbe più”.
“Ma finora non è stato trovato, vero?”.
“No, no, il milione di dollari è ancora lì, e noi continuiamo a fattorizzare i numeri in modo lento. Se vogliamo dirla tutta, è possibile che la dimostrazione della congettura P vs NP sia stata trovata da qualche matematico, il quale magari è stato pagato a peso d'oro dalla NSA per non rivelare l'informazione a nessuno. Ma questo è complottismo, e comunque noi poveri mortali non lo sapremo mai…”.
“Ma dai, figuriamoci”.
“Guarda che è già successo: alcune tecniche di crittanalisi sono state secretate dalla NSA e rese pubbliche solo in tempi recenti, dopo che sono state riscoperte da altri studiosi”.
“Wow, sembra roba da spie!”.
“Già. La seconda guerra mondiale è stata vinta anche grazie ai crittanalisti, per dire”.
“Che roba”.
“Vogliamo tornare al nostro metodo veloce per vedere se un numero è primo?”.
“Ok. Come si fa?”.
“Ti ricordi il teorema di Fermat?”.
“Sì, diceva che se un numero p è primo, allora ap-1 ≡ 1 mod p”.
“Bene, ribaltalo”.
“Eh?”.
“Come dicono i logici, trova la proposizione contronominale”.
“Ah, se pensi che adesso sia più chiaro…”.
“Insomma, fai come si fa nelle dimostrazioni per assurdo. Cosa puoi dire se succede che ap-1 è diverso da 1 modulo p?”.
“Ah, posso dire che certamente p non è primo, perché se lo fosse allora ap-1 dovrebbe essere congruente a 1”.
“Molto bene. Questo è già un test di non primalità”.
“Aspetta, aspetta, non ho mica capito. Il numero di cui devo testare la primalità qual è? È a oppure p?”.
“Il numero è p. Ti faccio un esempio, supponiamo che tu debba analizzare il numero 341, vuoi sapere se è primo”.
“Va bene”.
“Questo è p. Ora scegli a = 2, per esempio. Ho scelto un numero qualunque, più piccolo è meglio è. Naturalmente devo prenderlo primo rispetto a p, come dice il teorema di Fermat”.
“Va bene, 2 non divide 341. Adesso?”.
“Adesso calcolo 2340 mod 341”.
“E come faccio?”.
“Non è un problema, nemmeno di memoria: puoi fare un programmino che calcola la potenza per moltiplicazioni successive, e dopo ogni moltiplicazione calcoli il modulo: in questo modo il numero non diventa mai troppo grande. Comunque molte calcolatrici lo fanno, anche quella di windows”.
“Ah, ok. Provo: risulta 1”.
“Peccato”.
“Come peccato?”.
“Se risulta 1 significa che non possiamo dire niente, solo se non risulta 1 allora possiamo concludere che il numero non è primo”.
“E allora come facciamo?”.
“Prova con un altro valore di a, per esempio a = 3. Quanto fa 3340 mod 341?”.
“Dice che fa 56”.
“Perfetto. Quindi 341 non è primo”.
“Fantastico, l'abbiamo trovato senza calcolare i fattori di 341. Ho capito”.
“Purtroppo questo non è proprio un test di primalità, anzi; come ti dicevo è un test di non primalità”.
“Eh, non va mica bene. Il programma su internet riesce invece a scoprire se un numero è primo, non solo se è composto”.
“Infatti.”.
“Ma allora come funziona?”.
“Ora ti dirò qualche inesattezza, ma solo per capire l'idea di base. Poi mi correggerò e ti dirò come stanno le cose con precisione”.
“Va bene”.
“Allora, abbiamo detto che se il test di Fermat restituisce 1, non possiamo dire niente del numero: insomma, potrebbe essere sia primo che composto”.
“Giusto”.
“Allora, se un numero non è primo, risulta che nel cinquanta per cento dei casi il test fornisce una risposta uguale a 1, nell'altro cinquanta per cento dei casi invece il test fornisce una risposta diversa da 1, e quindi ci assicura la non primalità. Questa è una inesattezza, ma prendila per buona adesso”.
“Va bene”.
“Quindi se il primo tentativo su un numero ti dà un 1, ciò significa che il numero non è primo con probabilità uguale a 1/2”.
“Giusto, e quindi io non so niente”.
“Certo. Supponi di ripetere il test con un'altra base, e di nuovo trovi 1. Ora la probabilità che il numero non sia primo diventa 1/4, al terzo tentativo diventa 1/8, e così via”.
“Bè, però non ho la certezza”.
“No, certo, ma ti bastano 10 passi per arrivare a una probabilità che il numero sia primo del 99.9%. E 10 passi sono pochi, fanne qualcuno in più e la probabilità di sbagliare diventa più bassa della probabilità che ti cada un meteorite sulla testa, o che il tuo computer abbia sbagliato i calcoli, o che un ladro indovini la tua password tirando a caso, al primo colpo”.
“Ok, va bene, ai fini pratici magari può anche andar bene, ma non mi dire che un Vero Matematico si accontenta così”.
“Ah, no, certo che no. Anche perché quello che ti ho detto non è del tutto vero”.
Nessun commento:
Posta un commento