Introduzione

A.Shamir, R.L. Rivest, L.M. Aldeman

 

 

In questa serie di lavori sull'aritmetica presenteremo
alcune idee elementari riguardanti i numeri primi ed alcune loro applicazioni. Con il termine “elementari” intendiamo specificare che le tecniche che utilizzeremo non fanno uso dell'analisi matematica o dell'algebra lineare e non che i risultati che presenteremo siano semplici o banali. In particolare cercheremo di coniugare il rigore con la semplicità dell'esposizione poiché siamo convinti che gli argomenti trattati siano comprensibili a chiunque abbia voglia di dedicarci un po' di tempo ed anche che, d'altra parte, per capire davvero le cose sia necessario guardarle dall'alto, cioè con maggiore generalità. Per questo motivo, abbiamo incluso alcuni approfondimenti, nella speranza che i lettori non si fermino al primo livello, ma cerchino di andare oltre.

Le argomentazioni che presenteremo sono classiche, e sono diventate rilevanti anche dal punto di vista pratico dopo il 1975, ossia dall'avvento della crittografia a chiave pubblica. Cercheremo quindi in questa sede di introdurre le proprietà dei numeri primi che hanno rilevanza crittografica, senza però dimenticare di inquadrarle in una teoria più generale e completa, che ha un interesse intrinseco anche se, al momento, non trova applicazioni pratiche.

Uno degli aspetti più affascinanti, a nostro avviso, della teoria dei numeri primi sta nel fatto che ha la sua origine in un contesto discreto (i numeri interi positivi) ma, per averne una comprensione non superficiale, è necessario introdurre concetti dell'analisi matematica, che tratta prevalentemente grandezze continue. Per poi averne una comprensione profonda, si deve fare ricorso all'analisi complessa, apparentemente molto remota dal problema originale. In queste note tratteremo parte delle interrelazioni dell'aritmetica con l'analisi reale.

Per motivi di spazio, non parliamo di congruenze, pur utilizzando la nozione e le proprietà: rimandiamo alla trattazione che si trova nel Capitolo 2 di Conway e Guy[3], oppure a quella in [11].

Per quanto possibile, daremo riferimenti bibliografici in lingua italiana, ma desideriamo ricordare ai Lettori che non ce ne sono moltissimi. Quando non è possibile fare altrimenti, e limitatamente agli approfondimenti suggeriti, daremo qualche riferimento anche in inglese.

 

1 Notazioni

Per prima cosa fissiamo alcune notazioni che useremo in seguito.

Notazione 1.1 (Divisibilità) Diremo che l'intero a divide l'intero b se esiste un intero c tale che a·c=b, e in questo caso scriveremo a|b.

Osserviamo che non chiediamo che a o b sia positivo, né diverso da zero. Consideriamo note le proprietà elementari della Divisibilità. Per completezza, ricordiamo anche la definizione di congruenza, osservando al tempo stesso che è una relazione di equivalenza.

Notazione 1.2 (Congruenza) Dato un intero positivo n, diremo che l'intero a è congruo all'intero b modulo n, e scriveremo ab mod n, se n|a - b.