Dobbiamo arrangiarci: dobbiamo spulciare l'elenco dei numeri e scartare, nel modo più veloce possibile, i numeri che non sono primi; ovviamente quelli che rimarranno saranno i primi che stiamo cercando. Tutto qua.
«Sembra facile».
«Lo è, almeno all'inizio».
«Capirai…».
«Dico davvero: il più semplice sistema per generare numeri primi si chiama crivello di Eratostene».
«Crivello».
«Sì, si chiama così. Se vuoi, setaccio. Prende tutti i numeri da 1 fino a N, e separa quelli buoni da quelli cattivi».
«E come fa?».
«In un modo semplicissimo: prima di tutto, non parte davvero da 1, parte da 2».
«Va bene, sappiamo che 1 non è un numero primo».
«E poi procede così: legge il primo numero della lista…».
«Cioè 2».
«All'inizio è 2, poi l'algoritmo va avanti sempre alla stessa maniera. Per questo dico che prende il primo numero della lista: la prima volta è 2, poi però questo numero cambierà».
«Ok. Dopo aver preso il primo numero della lista, cosa fa?».
«Lo lascia stare lì dov'è, lo dichiara primo, ma cancella tutti i numeri che lo seguono e che sono suoi multipli».
«Cioè cancella 4, 6, 8, eccetera?».
«Esatto. Possiamo dire che, dato che il primo numero è 2, l'algoritmo procede a salti di lunghezza 2 e cancella tutto quello che trova».
«Sembra una cosa rapida».
«Molto rapida: non devi fare nessun tipo di operazione, solo saltare avanti e cancellare».
«Bene, e arrivati alla fine cosa succede?».
«Si ricomincia da capo, passando al successivo numero della lista che non è stato cancellato».
«Cioè 3».
«Esatto. E si va avanti a passi di 3, cancellando tutto quello che si trova».
«Ma il 6 era già stato cancellato prima».
«Non importa, il suo posto è sempre lì, e se cancelliamo due volte non succede niente. Sprechiamo tempo, in realtà, ma non sbagliamo».
«Ho capito. Poi si passa al 4».
«Eh, no».
«Ah, giusto, il 4 è già stato cancellato prima. Allora c'è il 5, poi ci sarà il 7, e così via».
«Esatto. I numeri che incontri sono i numeri primi, e cancelli tutti i loro multipli».
«Semplice».
«Nella realtà ci sono poi tante piccole ottimizzazioni che lo velocizzano un po'».
«Ah. Robe complicate?».
«Non tanto. Ad esempio, invece di partire dal primo numero della lista si può partire dal suo quadrato, e procedere poi a salti».
«Perché».
«Immagina di essere arrivato al numero 11».
«Il quadrato è 121».
«Certo. In teoria dovresti partire da 11 e eliminare tutti i suoi multipli».
«Il primo è 22, allora».
«Giusto, uguale a 11 per 2».
«Ah, ho capito! Dato che è multiplo di 2, è già stato eliminato prima!».
«Esatto. Poi ci sarebbe 33…».
«Che è stato eliminato quando sono stati cancellati tutti i multipli di 3. Ci sono: il primo numero da considerare è 11 per 11, cioè 121».
«Benissimo. Un altro trucchetto è quello di elencare solo i numeri dispari, tanto sappiamo che i numeri pari, a parte 2, non sono primi. Poi però si procede a salti di ampiezza doppia».
«Mh, perché?».
«Pensa al numero 3: se procedi a passi di ampiezza 3 ottieni 6, 9, 12, 15, e così via. Vedi che un termine ogni due è pari».
«Ed è già stato eliminato dalla lista! Ho capito».
«Questo metodo può poi essere generalizzato utilizzando la cosiddetta wheel factorization».
«Che sarebbe?».
«Si fa prima a fare un disegno che a spiegarlo:».
«Dovrei capire?».
«Guarda bene: è stato scelto come base il numero 30, e tutti i numeri sono stati scritti in cerchio».
«Vedo che il primo cerchio contiene tutti i numeri da 1 a 30, infatti».
«Esatto. Poi il secondo quelli da 31 a 60, e così via».
«Ah, giusto. In pratica li hai raggruppati secondo il resto della divisione modulo 30».
«Benissimo! Vedo che ti ricordi qualcosa, alla fine!».
«Eh, sì. Devo dire che mi hanno aiutato quelle uguaglianze scritte in alto a destra: ho riconosciuto la divisione per 30».
«Proprio così: vedi che ad esempio c'è scritto che 94 è uguale al prodotto di 3 per 30, più 4».
«Sì: vuol dire che 94 diviso 30 ha come quoziente 3 e resto 4».
«Perfetto. A noi interessano i resti: i soli resti che possono generare numeri primi sono 1, 7, 11, 13, 17, 19, 23 e 29».
«Mi sfugge il motivo per cui 3 e 5 sono esclusi dalla lista: quelli sono numeri primi».
«Certo, e il programma ne terrà conto. Ma ogni altro numero che ha resto 3 oppure 5 nella divisione per 30 non sarà primo».
«Mh, fammi capire».
«Un numero che ha resto 3, ad esempio, si può scrivere come 30h+3, cioè 3(10h+1)».
«Ah, certo: è multiplo di 3».
«Esatto. E un numero che ha resto 5 sarà 30k+5, uguale a 5(6k+1)».
«Multiplo di 5».
«Quindi i possibili numeri primi possono trovarsi solo nelle zone non colorate di giallo nella figura».
«Bello. Ma come facciamo con il crivello? Se, quando abbiamo tolto i multipli di 2, abbiamo detto che potevamo procedere a salti di ampiezza 2, ora come funziona?».
«Ecco, ora è più difficile, in effetti. Funziona in questo modo: prima di tutto, indichiamo con ki i numeri interessanti, cioè i nostri 1, 7, 11, 13, 17, eccetera, fino a 29».
«Bene».
«E indichiamo con M il numero che ha generato la ruota».
«Cioè 30».
«Esatto. Allora, se stiamo analizzando un numero primo p e vogliamo cancellare tutti i suoi multipli, dobbiamo risolvere questa equazione:».
Mm + ki = pn.
«Fammi capire…».
«A destra dell'uguale, al variare di n, ottieni tutti i multipli di p».
«E fin qua ci siamo».
«A sinistra invece hai tutti i numeri che sono uguali a ki modulo M. Cioè tutti i numeri non evidenziati di giallo nella ruota».
«Ah, ora ci sono: prima ho tutti i ki, poi tutti i 30+ki, eccetera».
«Sì: in pratica m è un contagiri».
«Perfetto, ci sono. Dicevi che dobbiamo risolvere l'equazione?».
«Sì, dobbiamo trovare il modo di utilizzare solo i multipli di p che cadono sulle zone non gialle della ruota».
«E come si fa?».
«Per prima cosa si riscrive l'equazione così: Mm = -ki mod p».
«Fin qua ci sono».
«Poi si calcola M-1 mod p».
«Mh. Per esempio? Come sarebbe 30-1 mod 7?».
«Sarebbe 4, prova a verificare».
«Dunque, 4 moltiplicato 30 fa 120, che diviso per 7 fa 17 con resto di 1. Giusto!».
«Esiste un metodo generale per calcolare questo M-1, quindi non ci sono problemi. Una volta trovato questo valore, si calcolano questi altri numeri:».
mi = M-1(-ki) mod p
«E cosa ce ne facciamo?».
«Ci servono per calcolare finalmente m, che risulta uguale a pj + mi».
«Ho capito. Anche se mi piaceva di più l'idea originale».
«Quella è certamente più semplice e immediata da capire, queste che abbiamo visto sono piccole migliorie che velocizzano un po' i conti, al prezzo di una meno immediata comprensibilità».
«E si può fare di meglio?».
«In che senso? Vuoi sapere se esistono algoritmi più veloci?».
«Sì».
«Esistono, ma per capire come funzionano dovremo fare un lungo passo verso l'alto».
«Eh?».
«Ci sarà da astrarre un po', pur cercando di continuare a capire quello che succede».
«Mh, prevedo complicazioni».
«Complicazioni che ci porteranno a scorgere una piccola parte di ciò che genera le ombre che di solito osserviamo».
6 commenti:
Cosa significa "mod"? Non lo capisco...
P.S.: complimenti per il blog!
Un'ultima cosa: il disegno non appare, almeno sul mio computer!
mod è il resto della divisione (ho indicato un link che parla di questo). Il disegno è un file .svg, su quale browser lo guardi? Sotto chrome e firefox funziona. (Acc, vedo che sotto internet explorer non si vede, mah)
OOOK! Allora i conti non li capisco: ho sperato fino all'ultimo che mod fosse qualcos'altro! Vediamo: 30^-1=1/30 o sbaglio? Ma mod si usa anche con numeri non interi? Non riesco a capire da dove salta fuori il 4. Comunque da adesso userò firefox o Chrome! Grazie!
No, in questo caso 30^-1 è quel numero che moltiplicato per 30 dà come risultato 1 mod 7. Significa che se divido il risultato per 7, ottengo come resto 1.
Allora il numero cercato è 4, perché 4*30 fa 120, che diviso 7 dà proprio resto 1.
Insomma, in un orologio con 7 ore se, partendo da 0, aggiungi per 30 volte 4 ore, arrivi su 1.
Ora ho capito!! Grazie mille!!!
Posta un commento