Crivello di KGB

Tutti o quasi conoscono il crivello di Eratostene per individuare i numeri primi. Si tratta quindi di un metodo molto semplice e lento: in pratica, in un intervallo da 1 a N, si eliminano, marcandoli in qualche maniera, tutti i multipli di 2, poi di 3, poi di 5, etc fino a radice di N. Tutti i numeri che non sono stati marcati sono primi.

Quando un paio di anni fa lavorai al pezzo Ironia matematica mi resi conto che i miei piccoli teoremi potevano essere utili a individuare numeri primi. Ci lavorai per qualche giorno sfornando un paio di programmi che trovavano numeri primi (*1): poi lasciai perdere e mi interessai ad altro ripromettendomi di tornare a lavorarci con calma: oggi ho deciso di rimetterci le mani e di spiegare il relativo algoritmo (*2)...

I teoremi che uso sono:
(C1)
Se MCD(I,N)=1, dato J=N Mod I, allora MCD(I,J)=1
e
(T2)
Se MCD(I,J)=1 con I>J allora MCD(I,I-J)=1

Prima di tutto faccio notare che I e N possono essere scelti come si vuole, purché il loro MCD sia 1, e il teorema è comunque valido. Ricordo anche che due numeri con il MCD uguale a 1 sono fra loro primi.
Ecco allora che l'idea è molto semplice: costruire I e N in maniera che siano prodotti di due insiemi di numeri primi (detto “basso” quello usato per calcolare I e “alto” quello per calcolare N) distinti fra loro (in maniera che il MCD sia uguale a 1); a questo punto usare le formule di (C1) e (T2) (cioè K1=N Mod I e K2=I-K1) per trovare una coppia di numeri che saranno primi rispetto a I. Invece tali numeri andranno verificati rispetto ai fattori di N: se però scegliamo opportunamente i nostri numeri questa operazione potrà addirittura essere scartata!

L'idea è usare come fattori di I i numeri primi (e loro potenze!) da P2 a Pi e per N i numeri primi da P(i+1) a P(i+j) (*3).
Il vantaggio di questo sistema è che se i valori ricavati con le formule di (C1) e (T2) sono maggiori di P(i+j) e minori di P(i)² allora sono sicuramente primi senza bisogno di ulteriori controlli (*4).

Facciamo un esempio banale e partiamo con I basato su {P2} e N basato su {P3} (*5). Saranno primi tutti i K1, K2 maggiori di P(i+j)=3 e minori di P(i)²=9.

Fig. 1
Come si vede dalla tabella si individuano i primi 5 e 7.

Modificato 5/5/2013: Rileggendo il pezzo insieme a mio padre per spiegargli alcuni particolari mi sono accorto che blogger.it se ne era "mangiata" una parte (impazzito a causa dei simboli "maggiore" e "minore" che infatti adesso evito accuratamente!). La parte mancante era la seguente:

Adesso vediamo cosa succede con I basato su {2, 3} e N basato su {5}. Saranno sicuramente primi i K1, K2 maggiori di 5 e minori di 25.

Come si vede dalla tabella si individuano immediatamente i primi 7, 11, 13, 17, 19 e 23; invece 25 sarebbe primo se non divisibile per 5 mentre per 43, 53 e 67 l'algoritmo non può dire nulla.

Se invece scelgo I basato su {2} e N basato su {3, 5}. Saranno primi i K1, K2 maggiori di 3 e minori di 9; dovrò verificare quelli minori di 25 e non potrò dire niente per quelli maggiori...

Come si vede dalla tabella si individuano immediatamente come primi 5 (già noto) e 7; 11, 13, 17 e 19 sono primi dopo aver verificato che non sono divisibili per 3 e 5.

Fine modifica

Adesso vediamo cosa succede con I basato su {2,3,5} e N basato su {7}. Saranno primi i K1, K2 maggiori di 7 e minori di 49 (*6).

Ecco che iniziano ad apparire alcuni limiti di questo algoritmo:

1. Non si sa quale sia la maniera migliore per selezionare gli insiemi di numeri primi basso e alto
2. Non si sa quali siano gli esponenti (comunque maggiori o uguali a 1) da assegnare ai fattori dell'insieme basso
3. Non si sa quando si sono trovati tutti i numeri primi compresi fra P(i+j) e P(i+1)^2

È comunque possibile scrivere un programmino che partendo da pochi numeri primi (ad esempio 2, 3 e 5) ne trovi altri che aggiungerà iterativamente all'insieme di partenza. Il problema è che non sapendo quanto numeri primi devono essere trovati a ogni iterazione, prima o poi, se ne salta qualcuno e si formano così dei “buchi” (diciamo, per esempio, che “dimentichiamo” di trovare Pz) negli insiemi di partenza: questo fa sì che all'iterazione successiva vengono calcolati come primi, ad esempio, le potenze di Pz (e se poi ci siamo dimenticati anche Py allora l'algoritmo può restituire come primi anche i prodotti delle potenze di Pz e Py, etc...).

Nel frattempo ho fatto qualche altro esperimento e mi sono reso conto di una semplice verità: se si sceglie l'insieme basso in maniera che I (almeno quando gli esponenti dei vari fattori sono 1!) sia minore di P(i+j)^2 allora nessuna iterazione è “persa” perché K1 sarà a sua volta minore di P(i+j)^2 e quindi basterà verificare che non sia divisibile per nessun elemento dell'insieme “alto”.

Vedi esempi:

Come si può vedere, con l'insieme alto uguale a {11}, per la maggior parte dei K1 e K2 (caselle colorate in rosso) trovati non si può dire niente...


Al contrario, con l'insieme alto uguale a {7, 11}, quasi tutti i K trovati sono utili: solo per quelli colorati in blu (maggiori di 49 ma minori di 121) bisogna verificare che non siano divisibili per 7 o 11 (tutti i fattori dell'insieme alto).

Mi sono reso conto di non essere stato troppo chiaro: non è facile descrivere un algoritmo a parole!
Se c'è interesse posso pubblicare un programmino Java che fa quanto detto: fatemi sapere!
...
Non importa: il codice apparirà nel pezzo di domani...

Conclusione: sicuramente questo procedimento sarà già noto da n secoli: come spesso mi capita probabilmente ho solo "reinventato la ruota", se qualcuno conosceva già questo algoritmo me lo faccia sapere perché sono curioso!

Nota (*1): con un grosso “se” che non ho voglia di stare a spiegare...
Nota (*2): che ho modestamente battezzato crivello di KGB!
Nota (*3): con P1=1, P2=2, P3=3, P4=5, P5=7, P6=11 etc...
Nota (*4): altrimenti, se minori di P(i+j)², sono primi se non divisibili per i primi dell'insieme alto; se maggiori di P(i+j)² non possiamo dire niente (potrebbero essere primi oppure prodotti di primi maggiori di P(i+j)...)
Nota (*5): con la notazione {} intendo i possibili prodotti dei numeri primi, e delle loro potenze. Cioè se si ha {A,B,C} allora intendo A^i*B^j*C^k con i, j e k maggiori o uguali a 1.
Nota (*6): mi sono accorto che nell'immagine ho colorato in rosso 47 che, essendo minore di 49, dovrebbe invece essere colorato in verde!

Share