Pagina:Dalle dita al calcolatore.djvu/274

Da Wikisource.
Jump to navigation Jump to search
252 xiii. i calcolatori

ce che se un numero N è primo e B è un altro numero intero, allora bn − b è multiplo di N; da questa affermazione si può trarre un test che ci dice se B sia primo o no.

I numeri che superano questo tipo di test vengono detti pseudoprimi, perché, al loro interno, esistono ancora i numeri cosiddetti di Carmichael, che pur superando il test non sono primi. Questi numeri sono molto pochi. I numeri primi inferiori a 20 miliardi sono esattamente 882.206.716: se si eseguisse il test di Fermat in base 2 su tutti i numeri compresi tra 1 e 20 miliardi, la percentuale di errori, e cioè di numeri pseudoprimi, sarebbe di circa uno su un milione.

Negli anni settanta due studiosi dell’Università di Berkeley misero a punto una variante del test di Fermat per dimostrare la primalità di un numero, e dimostrarono che se un numero passava il loro test la probabilità che si trattasse di uno pseudoprimo era inferiore o uguale a uno diviso 10 30, una probabilità tale da essere molto superiore al livello di “sicurezza” di molte “dimostrazioni”. Alcuni hanno osservato che un livello tale di “incertezza” (ma sarebbe più corretto definirla “certezza”) potrebbe essere accettato come dimostrazione matematica della primalità del numero che passi il test.

Questo risultato pone ovviamente una serie di problemi che riguardano il concetto stesso di certezza matematica e di dimostrazione: il livello di certezza raggiunto mediante il test proposto è tale da imporre una distinzione tra i concetti di dimostrazione e di certezza, separandoli. In questo modo però si mette in discussione una parte consistente dell’intelaiatura stessa del pensiero matematico, abituato a collegare la certezza solo alla dimostrazione, e a separare nettamente le affermazioni probabili da quelle dimostrate e perciò considerate certe.

Si può dire tranquillamente che risultati di questo genere impongono un ripensamento dalle fondamenta