G. C. Barozzi, Aritmetica: un approccio computazionale,

Aritmetica: un approccio computazionale,
Springer, 2007
di Giulio Cesare Barozzi

Lo studio dell'aritmetica sembrava ormai relegato alla scuola di base. In tempi recenti la crittografia e la generazione di codici di difficile decifratura hanno riportato in auge alcuni temi legati all'aritmetica elementare, come la scomposizione in fattori primi dei numeri interi. Il libro del prof. Barozzi, scritto in una prospettiva didattica più che di ricerca, è un contributo all'analisi di argomenti classici della teoria elementare dei numeri.

Il libro come ogni buon manuale, comincia da zero, ossia dagli assiomi di Peano per i numeri interi naturali e di ogni tema, anche di quelli elementari, presenta un listato commentato in TI-BASIC (il linguaggio delle calcolatrici grafico-simboliche della Texas Instruments) e un diagramma di flusso.

Nel primo capitolo (Numeri interi) sono presentati diversi algoritmi per il calcolo del MCD e del mcm. Il secondo capitolo è dedicato all'aritmetica modulare particolarmente utile nella crittografia: x è congruente a y modulo m se la loro differenza è un multiplo di m. Vengono presentati gli algoritmi per il calcolo del reciproco di un numero modulo m, ossia del numero s per il quale (mod m); per il teorema cinese dei resti che permette di individuare un numero a partire dai suoi resti; per il calcolo della potenza di un numero modulo m.

Il terzo capitolo è dedicato ai numeri primi: il problema della distribuzione dei numeri primi, la funzione

definita come il numero di numeri primi non superiori a n; alcuni algoritmi sulla scomposizione in fattori primi di un numero. In questo capitolo sono descritti anche i principi di base della crittografia a chiave pubblica messa a punto nel 1977 da R.L. Rivest, A. Shamir e L.M. Adleman.

Questi ricercatori osservarono che era possibile basare un sistema crittografico che si basa sulla difficoltà di scomporre in fattori primi un numero molto grande, ad esempio un numero ottenuto dal prodotto di due primi ciascuno dei quali è costituito da un centinaio di cifre. A chiave pubblica significa che lo strumento per la codifica dei messaggi (la chiave appunto) può essere reso di pubblico dominio perché per decodificare il codice occorre possedere un'informazione aggiuntiva che sebbene contenuta nelle informazioni pubbliche richiede poi tempi proibitivamente lunghi per poter essere dedotta. Un qualunque messaggio può essere trasformato in una stringa di cifre (lo si può per esempio trasformare secondo il codice ASCII). Questa lunga stringa di cifre può essere suddivisa in sottostringhe in modo tale che ciascuna di esse non superi per lunghezza di cifre un numero naturale prefissato.

Il problema diventa allora quello di inviare numeri naturali non superiori a un massimo prefissato n, per il quale

, con e due numeri primi distinti. Sia la stringa da trasmettere. Per l'estensione di Eulero del teorema di Fermat sappiamo che mod n. Supponiamo di poter scrivere come prodotto di due interi e , allora . A questo punto il mittente invia mod n il ricevente calcola mod n che corrisponde ad . A questo punto il problema della crittografia diventa quello di ottenere numeri primi grandi, con centinaia di cifre, a un 'basso costo' di calcolo.

Nel libro sono indicati i teoremi e gli algoritmi di base dei cosiddetti test di primalità dei numeri.

Il quarto capitolo del libro è dedicato ai numeri razionali. In appendice sono riportati listati in TI-basic e una sintesi dei principali comandi relativi alla teoria dei numeri in Derive, Maple, Mathematica.

Il libro per la chiarezza espositiva e la rigorosità della trattazione è consigliato anche ai tanti appassionati dilettanti di calcolo dei numeri primi.