backup del Post

Il crivello dopo Eratostene

Non ho mai capito perché a scuola, almeno quando a scuola ci andavo io, gli insegnanti erano così felici di parlare del crivello di Eratostene, un metodo per trovare tutti i numeri primi inferiori a un limite dato. Secono me la ragione recondita è che usare il crivello è un esercizio di pazienza degno di un monaco zen. Pur continuando a dover essere pazienti, però, si possono trovare crivelli di tipo almeno a prima vista ben diverso!

Innanzitutto, per chi non sa di che si parli, vi spiego rapidamente cos’è il crivello di Eratostene. Anzi, vi dico in due parole chi era Eratostene: un matematico ellenista, più o meno del periodo tra Euclide e Archimede, che se ne stava ad Alessandria nella Grande Biblioteca ed è soprattutto noto per avere stimato con una discreta precisione la circonferenza della Terra – che i greci sapevano perfettamente essere sferica, che credete?

Come ho accennato prima, il suo crivello è un algoritmo – anche se lui non lo chiamava certo così – per ricavare tutti i numeri primi inferiori a un numero dato. Le istruzioni operative sono semplici, e raffigurate nella figura qui sopra. Innanzitutto si scrivono tutti i numeri da 2 al limite massimo che interessa: vi ricordo che per i greci 1 non era un numero ma il generatore dei numeri, e quindi non si facevano tanti pipponi se 1 fosse o no un numero primo. Poi si prende il primo numero, 2, e si cancellano tutti i suoi multipli: nella figura li ho colorati di verde. Si passa al primo numero rimasto, 3, e si colorano i suoi multipli: in questo caso ho usato il giallo. Naturalmente ci saranno numeri che verranno colorati due volte: non importa. Proseguendo, il primo numero rimasto è il 5 (azzurro), seguito dal 7 (rosso); dopo aver tolto i mulltipli di quei numeri mi sono fermato perché ero interessato ai numeri fino a 100 e il quadrato del numero seguente, 11, è maggiore di 100; anzi avrei potuto aggiungere altri 20 numeri. A questo punto, i numeri rimasti sono tutti e soli i primi nell’insieme di partenza.

È chiaro come mai l’algoritmo funziona: tutti i numeri che si tolgono sono composti, e li abbiamo tolti tutti perché per esempio nel nostro caso non possiamo aver dimenticato 11·p con p minore di 11, perché l’avremmo già trovato ed eliminato come p·11. È però vero che il costo computazionale dell’algoritmo è piuttosto alto, richiedendo un numero di operazioni dell’ordine del massimo numero che si vuole verificare, cioè O(N) operazioni, e un costo di memoria pari a O(N^1/2(log log N)/log N) bit di memoria. Non è però che in più di duemila anni si sia così migliorata la ricerca. Eulero si è limitato a fare una modifica all’algoritmo (la trovate su Wikipedia in inglese) per evitare di cancellare più volte lo stesso numero; i migliori algoritmi attuali, come il crivello di Atkin, hanno costo computazionale pari a O(N/log log N) operazioni e N^{1/2 + o(1)} bit di memoria. Paradossalmente così per verificare se un numero è primo si preferisce usare un test probabilistico di primalità che non dà la certezza assoluta ma quasi; un matematico puro storce immediatamente il naso, ma i numeri primi grandi non servono a loro bensì agli informatici per generare le chiavi crittografiche e in questo caso una probabilità di non primalità intorno a una parte su 10³⁰ non dà soverchi problemi.

Quello che però sono in pochi a sapere è che si può usare un crivello geometrico per generare i numeri primi! Il metodo è stato esposto da due matematici russi, Yuri Matiyasevich e Boris Stechkin, e prevede l’uso di una parabola, come si può vedere nella figura qui sotto, tratta dal loro articolo di presentazione: per comodità la parabola è stata disegnata in orizzontale anziché in verticale, e quindi la sua equazione non è la classica y=x² ma x=y². Sull’asse delle x si indichino tutti i numeri naturali; sulla parabola si segnino invece quelli che hanno un valore intero per y il cui valore assoluto sia maggiore o uguale a 2. L’operazione che si deve ora fare consiste nel disegnare tutti i segmenti che uniscono tra di loro due punti segnati sulla parabola, uno nel semipiano positivo e uno negativo. Questi segmenti toccheranno l’asse delle x in un punto; tutti i punti a coordinata intera che non vengono toccati da nessun segmento corrispondono ai numeri primi.

Come funziona tutto ciò? Beh, la cosa è relativamente semplice. Se un numero n è esprimibile come prodotto ab e prendiamo i punti etichettati a e b sui due rami della parabola, le loro coordinate cartesiane sono (a²,a) e (b²,−b). È facile vedere che l’intersezione della retta che passa per quei due punti con l’asse delle x sarà il punto (ab,0), dal che si ottiene immediatamente la tesi del teorema (e si capisce perché non si devono usare i due punti di ordinata 1 e −1…) L’utilità pratica di questo crivello è pressoché nulla, però dal punto di vista didattico la figura è molto interessante, perché permette di visualizzare la fattorizzazione in modo diverso dal solito, e così aiutare la comprensione matematica… voi che ne pensate?