«L'idea che sta sotto al crivello di Atkin, che sarebbe il crivello che migliora quello di Eratostene, è questa: invece di utilizzare la forma quadratica xy, se ne utilizzano delle altre per le quali i calcoli sono più rapidi».
«Quali?».
«Atkin e Bernstein, i due che hanno pubblicato il loro studio sul nuovo crivello, ne hanno proposte tre, anche se dicono che se ne potrebbero usare delle altre».
«Addirittura tre».
«Eh, sì. Allora, le cose stanno così: tutto è riferito al modulo 60, i numeri vengono divisi in categorie in base al resto della divisione con 60».
«Quindi abbiamo 60 categorie».
«Ora le riduciamo un po', però. Dobbiamo arrivare a tre».
«Bene».
«Prima di tutto, tutti i resti pari li mettiamo nella stessa categoria».
«Perché?».
«Indichiamo con 2N il resto della divisione con 60: posso scrivere 2N perché immagino che sia pari. Allora questi numeri possono essere scritti come 60h+2N, e vedi subito che sono divisibili per 2. Quindi non sono primi (a parte 2, naturalmente)».
«Ah, giusto. Ma allora nella stessa categoria ci possiamo mettere anche quei numeri che hanno resto 3 e 5, per lo stesso motivo».
«Infatti, è così. E questa categoria non ci interessa: non contiene numeri primi, e quindi non la consideriamo più. Rimangono allora questi resti, coi quali costruiremo tre categorie interessanti:».
1, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59.
«E cosa ci facciamo?».
«Raggruppiamo anche questi: come ti dicevo, in tre classi diverse».
«Come sono fatte?».
«Eh, qui cominciano le cose strane. Per poter usare tre teoremi che ti racconterò dopo, le classi sono fatte così: nella prima ci vanno tutti i numeri uguali a 1 modulo 4».
«Vediamo, dovrebbero essere questi: 1, 13, 17, 29, 37, 41, 49, 53».
«Esatto. Nella seconda classe ci vanno i numeri uguali a 7 modulo 12».
«Mh, sono 7, 19, 31, 43».
«Proprio loro. Nella terza e ultima classe ci vanno i numeri uguali a 11 modulo 12».
«Sono i rimanenti: 11, 23, 47, 59».
«Bene. Ora, prima di enunciarti il primo teorema ti faccio una figura. Prendiamo un numero della prima classe, per esempio 13. Eccoti il grafico di 4x2 + y2 = 13».
«Vedo che hai evidenziato un punto».
«Sì, in realtà ce ne sono quattro, simmetrici. Uno solo è quello con coordinate intere positive. Ora, prima di trarre delle conclusioni, eccoti un altro numero, sempre uguale a 1 modulo 4: 65».
«Perché così grande?».
«Prima il grafico, poi ti spiego:».
«Uh, due punti».
«Sì, il teorema dice che se p è primo e non contiene fattori primi elevati al quadrato (lo so che è una condizione inutile, ma ci servirà dopo per costruire l'algoritmo) allora il numero di punti a coordinate intere positive che stanno sull'ellisse è dispari, e viceversa».
«Ah. E perché hai scelto proprio 65?».
«Perché coi valori minori di 65 gli unici esempi che riuscivo a farti erano di ellissi con zero punti a coordinate intere positive. Zero non è dispari, quindi il teorema funziona, ma c'era poco da disegnare».
«Va bene. Quindi l'algoritmo si deve occupare di contare i punti che stanno su quell'ellisse?».
«Esatto. Poi, dopo che lo ha fatto, deve togliere i valori che contengono fattori primi elevati al quadrato».
«Va bene. Questo però è quello che succede con la prima classe di numeri. Ce ne sono altre due, no?».
«Certo. Per la seconda, quella composta da numeri uguali a 7 modulo 12, vale lo stesso tipo di teorema, ma cambia la curva. Questa volta l'equazione da utilizzare è 3x2 + y2 = p».
«Mh, facciamo una prova».
«Eccoti la curva con p=7».
«Un solo punto. Vediamo che succede con un numero non primo?».
«Certo. Eccoti p=91».
«Due punti. Anche qui hai dovuto scegliere 91 perché coi numeri più piccoli non avresti trovato punti?».
«Esatto».
«Rimane la terza categoria, allora».
«Sì, quella dei numeri uguali a 11 modulo 12. Questa volta la curva da considerare è diversa, si tratta dell'iperbole di equazione 3x2-y2 = p. E, attenzione, solo quando x è maggiore di y, quindi in una zona limitata».
«Mh, vediamo i grafici».
«Questo è con p=11. Ho rappresentato anche la retta y = x: la zona che dobbiamo analizzare si trova al di sotto di quella retta, nel primo quadrante».
«Anche qui, un solo punto».
«E questo con p=143».
«Ah, vedo che hai rappresentato solo il primo quadrante».
«Eh, sì, altrimenti non si sarebbe vista bene la griglia. Ed ecco fatto, tutti i numeri ricadono in queste categorie, si tratta di contare quanti sono i punti a coordinate intere positive che stanno sulle curve — e, nel caso dell'iperbole, hanno ascissa maggiore dell'ordinata — e, se questi sono in numero dispari e se il numero che stiamo analizzando non contiene fattori al quadrato, allora è primo».
«Bleah».
«Sì, lo so, è complicato, ma è a questo che ci ha portati l'astrazione del crivello di Eratostene. Siamo partiti da un semplicissimo sistema di conteggio di numeri su una griglia, e siamo arrivati a contare punti su curve. Ma naturalmente i due autori dell'articolo non hanno mai parlato di curve, né mostrato dei grafici».
«Naturalmente».
«Loro parlano di domini a ideali principali, di forme quadratiche, di semigruppi quoziente, di mappe logaritmiche. Roba che per capirla bene servirebbe un intero corso di algebra. Chissà, forse si può trovare un metodo meno astratto di quello usato da Atkin e Bernstein per dimostrare i teoremi che vengono usati nel loro articolo».
«Dici quelli relativi alle due ellissi e all'iperbole?».
«Sì, quelli. Ti confesso che, dopo averci provato per un po', ci ho rinunciato».
«Ahi, ahi».
«Mi è bastato intuire come stavano le cose, e mi sono fidato. Del resto gli autori dicono che sono teoremi standard, e che li hanno inseriti nel loro lavoro solo per un senso di completezza. Comunque, danno per sottintese mille cose, sono dimostrazioni molto compresse. Ma, se vuoi, trovi tutto qui».
«No, grazie, mi fido anche io».
«Per concludere, Bernstein ha fatto una cosa carina: ha scritto una serie di programmi che tutti possono prelevare ed utilizzare. Io l'ho fatto, e devo dire che sono velocissimi. Sono qui».
«Ma, rispetto al crivello di Eratostene, c'è questo gran vantaggio?».
«Ti dirò, questo criterio non è così tanto più veloce. Gli autori hanno fatto una prova: per trovare tutti i numeri primi fino a N = 109 la loro implementazione del crivello di Eratostene ha impiegato circa 3.3·109 cicli, mentre quella del loro crivello ne ha impiegati 2.5·109».
«Quindi siamo sempre nell'ordine di N».
«In realtà l'ordine è N/log(log(N)). E questo è il meglio che oggi riusciamo a fare».
Se qualcuno volesse provare a cercare una dimostrazione decente dei teoremi che ho indicato qua sopra, si tratta dei numeri 6.1, 6.2 e 6.3 a pagina 1028 di questo articolo. Si potrebbe forse ragionare sugli interi di Gauss.
1 commento:
Auguri di un buon 2012!
Posta un commento