Numeri primi

(note a cura di Roberto Bigoni)

English version

1. I numeri primi

Come è noto dai primi studi aritmetici, i numeri primi sono i numeri naturali maggiori di 1 non risultanti dal prodotto di due numeri minori.

Questa definizione implica che 1 non è primo e che l'unico primo pari è 2.

I numeri primi sono infiniti, cioè non esiste il massimo numero primo. Una dimostrazione per assurdo di questo teorema si deve a Euclide.

I numeri naturali maggiori di 1 non primi sono detti numeri composti.

2. Il crivello di Eratostene

Il metodo concettualmente più semplice per ottenere l'insieme P_n dei numeri primi ≤ n (n> 2) è il crivello di Eratostene
(il crivello o vaglio o setaccio è un attrezzo per filtrare il grano macinato, separando la farina dalla crusca):

1. si inizializza l'insieme P_n contenente il numero 2;
2. si considerano successivamente tutti i numeri k, 2 < k ≤ n;
   se k non è divisibile per un numero p ∈ P_n, lo si immette in P;
3. al termine della procedura, P_n contiene tutti i primi p ≤ n.

Per stabilire se un numero dispari n è primo, cioè per controllarne la primalità, si può costruire l'insieme P_n e controllare se n è l'ultimo elemento di P_n.
Se si, n è primo; altrimenti è composto.

La seguente applicazione Javascript calcola i numeri primi ≤ n e l'n-simo numero primo.
Ovviamente, perché essa funzioni a dovere il vostro browser deve abilitare Javascript.
Se il vostro browser non permette i frames interni, potete accedere direttamente alla pagina dell'applicazione.
Se il tempo di calcolo supera i minuti indicati, potete provare ad aumentarli.

3. Il metodo di fattorizzazione di Fermat

Se n è molto grande, il crivello risulta impraticabile per quantità di memoria e tempo di calcolo richiesti. Sono stati quindi cercati e vengono cercati ancor oggi test di primalità diretti, cioè non richiedenti il calcolo di un numero enorme di primi.

Un primo test di primalità si può derivare da un algoritmo di fattorizzazione dovuto a P. de Fermat.

Dato il numero dispari n, il metodo di Fermat si basa sulla ricerca di due numeri h e k tali che

Se n è un quadrato perfetto, la soluzione è immediata perché il questo caso n è uguale al prodotto della sua radice quadrata per sé stessa e ovviamente n non è primo.

In caso contrario si può sempre esprimere hk come differenza di due quadrati:

quindi, posto

si ha

Il problema è risolto se si trova un numero a tale a²-n sia un quadrato perfetto.

A questo scopo si procede per tentativi:

• si assume come primo valore di a il primo numero naturale maggiore della sua radice quadrata;
• se a²-n è un quadrato perfetto il problema è immediatamente risolto;
• altrimenti si incrementa a di 1 finché a²-n non risulta un quadrato perfetto;
• a questo punto si calcola la radice quadrata di a²-n ottenendo b.

Ricavati a e b si ha

Se a-b = 1, n è primo; altrimenti i due fattori a-b e a+b (cioè h e k) sono diversi e minori di n, quindi il numero è composto.

4. I quadrati perfetti

Il metodo di fattorizzazione di Fermat richiede di controllare ripetutamente se un numero naturale n è un quadrato perfetto.

Non è possibile determinare direttamente questa proprietà di n.

In molti casi è tuttavia possibile escluderla abbastanza velocemente osservando che i residui modulo m, per un numero m prefissato, sono in numero abbastanza ridotto.

Ad esempio, i residui modulo 8 per i quadrati dei primi 100 numeri naturali, utilizzando WolframAlpha, sono

Anche senza una dimostrazione formale, si può tranquillamente congetturare che calcolando il resto della divisione di un numero naturale per 8, se il resto è diverso da 0, 1, 4, il numero non è un quadrato perfetto.

Un ulteriore esempio è fornito dall'insieme dei residui modulo 9.

Anche in questo caso si può tranquillamente congetturare che calcolando il resto della divisione di un numero per 9, se il resto è diverso da 0, 1, 4, 7, il numero non è un quadrato perfetto.

Ma il superamento di test di questo tipo è condizione necessaria ma non sufficiente a stabilire che n è un quadrato perfetto. È quindi utile per diradare il numero dei possibili quadrati perfetti, ma non conclusivo. Una procedura inevitabilmente più dispendiosa che fornisce la sicurezza può essere un algoritmo di bisezione.

1. Si considera la successione dei numeri naturali q_i che, iniziando da 4, è formata da numeri tali che ognuno di essi è il quadrato del precedente.

   

2. Se n coincide con uno dei q_i, n è un quadrato perfetto e la procedura finisce.
3. Altrimenti neanche √n coincide con un q_i ed è compresa tra due di questi termini:
   ;
4. Si pone
   
5. Si confronta n con il quadrato del valor medio m tra min e max:
6. • Se n=m², n è un quadrato perfetto, la sua radice quadrata è m e la procedura finisce.
   • Se max ≤ min+1, n è non è quadrato perfetto e la procedura finisce.
   • Se n < m² si pone max = m, altrimenti si pone min = m e si torna al passo 5.

Esempio.

Sia n = 40401

Si ha 40401≡1 (mod 8) e 40401≡0 (mod 9): quindi il numero supera i due test preliminari proposti. Si applica l'algoritmo di bisezione

passo 1	passo 2
passo 3	passo 4
passo 5	passo 6
passo 7	fine n è un quadrato perfetto; la sua radice quadrata è 201

5. Il test di primalità di Fermat

Un metodo più diretto di controllo della primalità è di un numero naturale, pure proposto da Fermat, si basa su un teorema enunciato da Fermat stesso, ma dimostrato successivamente da L. Euler, noto come Piccolo Teorema di Fermat.

dove (mod p) rappresenta il resto della divisione per p.

Una dimostrazione del teorema si può ottenere per induzione.

Il teorema stabilisce una condizione necessaria, ma non sufficiente. Cioè qualunque primo p verifica il teorema, ma possono esistere numeri composti c che verificano la congruenza . Questi numeri sono detti pseudoprimi di Fermat rispetto ad n. In particolare, gli pseudoprimi rispetto a qualunque n coprimo con c sono detti numeri di Carmichael.

Quindi, se un numero q non verifica il teorema rispetto ad un coprimo n, si può affermare che q è composto, ma se lo verifica non si può affermare che esso è primo, ma solo che è, probabilmente primo.

Se si sperimentano molti valori n con esiti sempre positivi, si può operativamente assumere q come primo.

6. Il test di primalità di Miller-Rabin

Il test di Fermat, anche con numerosi controlli, può fallire e indicare come primi numeri che invece sono composti.

Si può ridurre questo rischio e valutare la probabilità di ottenere una risposta corretta, osservando che perché un numero q>2, sia primo, q deve essere dispari e quindi q-1 è pari.

Ogni numero pari può essere scomposto nel prodotto di un numero dispari per una potenza di 2.

Dal teorema di Fermat, se q è primo e n coprimo con q, , si ha

da cui

quindi

Se questa radice è ≡ 1(mod q), allora la successiva sarà ≡ ±1 (mod q) e così via.

Se tutte le radici sono ≡ 1 (mod q), quindi anche n^d≡1 (mod q), q supera il test ed è probabilmente primo.

Se la prima radice non ≡ 1 (mod q) è ≡ -1 (mod q), q supera il test ed è probabilmente primo.

In caso contrario q è composto.

In definitiva, per stabilire se q è probabilmente primo:

• si sceglie a caso un numero n coprimo con q;
• se, con questo n, q non supera il test di Fermat, q è composto;
• si calcola n^d (mod q); se si ottiene 1, il numero è probabilmente primo;
• altrimenti si calcolano in modulo q le potenze con k decrescente da s-1 a 0. Se la prima di queste potenze non ≡ 1 (mod q) non è ≡ -1 (mod q), q è composto;
• altrimenti q supera il test ed è probabilmente primo.

La probabilità che un numero composto q passi il test è al massimo ¼. Dunque, ripetendo il test con altri valori di n, la probabilità che q li superi tutti decresce esponenzialmente.

7. Scomposizione di un numero naturale in prodotto di potenze di fattori primi.

Un numero naturale n o è primo o è composto.

Usando un test affidabile come quello di Miller-Rabin, si può decidere direttamente se è primo e quindi gli unici fattori sono 1 e n.

Se n è composto si può usare il crivello di Eratostene.

1. Si calcola l'insieme Q_n = {q₁, q₂, … q_n } dei numeri primi minori della radice quadrata di n.
2. Se n è divisibile per un q_i, si è individuato un fattore della scomposizione; si esegue la divisione e si controlla se il quoziente è ancora divisibile per q_i.
   Se si, si ripetono le divisioni finché non si ottiene un quoziente non divisibile per q_i. q_i appare nella fattorizzazione con esponente uguale al numero delle divisioni fatte.
3. Si riapplica la procedura all'ultimo quoziente ottenuto considerando i rimanenti elementi di Q_n.

Tuttavia, se n è molto grande, anche √n è grande ed è grande anche il numero degli elementi di Q_n il cui calcolo può richiedere tempi impraticabili.

In alternativa, con il metodo di Fermat:

1. n è espresso come prodotto di due numeri naturali h e k minori di n;
2. a loro volta h e k o sono primi o sono composti;
3. se sono entrambi primi, il loro prodotto è la scomposizione di n in prodotto di fattori primi;
4. in caso contrario si può applicare il crivello o il metodo di Fermat ai fattori composti e ripetere il procedimento finché non si ottengono solo fattori primi;
5. se al termine del procedimento un fattore compare più volte il prodotto dei fattori identici è sostituito da una potenza e il prodotto di queste potenze (con esponente ≥ 1) è la scomposizione di n in prodotto di potenze di fattori primi.

Il metodo di Fermat funziona in modo soddisfacente per numeri non molto grandi o, anche per numeri grandi, se i due fattori h e k sono entrambi prossimi a √n. In caso contrario può comportare tempi di calcolo impraticabili anche sui sistemi più veloci.

Per superare queste difficoltà sono stati proposti altri metodi di fattorizzazione, come, ad esempio, il seguente algoritmo dovuto a John M. Pollard.

8. L'algoritmo ρ (rho) di Pollard

Sia h un divisore di n.

Se, dati s₀ = a e la funzione f(s) = mod(s²+2,n), si costruisce la successione S in cui s_i+1 = f( s_i ), allora, dopo al massimo h+1 passaggi, si trova un s_s tale che s_s = s_k (k > s) e quindi gli elementi successivi si ripetono ciclicamente. Rappresentando gli elementi come nodi di un grafo, questo assume una forma che ricorda la lettera greca ρ (trascrizione latina 'rho', corrispondente alla nostra r minuscola, da cui il nome dell'algoritmo).

Ad esempio, dato n = 51, h = 3 è un divisore di n. Posto s₀ = 2, si ha

s₂ = s₆, quindi s₃ = s₇ e così via.

Se i ≠ j, s_j > s_i e s_j ≡ s_i (mod h), si ha:

• s_i = x h + a
• s_j = y h + a
• s_j - s_i = ( y - x ) h

e quindi

MCD ( s_j - s_i , n ) = h

Se, continuando l'esempio proposto, si costruisce una tabella dei valori assoluti delle differenze d_i,j = s_i - s_j tra tutti gli elementi s_k calcolati, si osserva che, per i ≠ j, solo in alcuni casi il MCD(d_i,j,n) è maggiore di 1 e che in questi casi MCD = 3, cioè h.

Quindi, scelti a caso s_i e s_j con i ≠ j, MCD(d_i,j,n) > 1, allora MCD(d_i,j,n) = h.

Si possono evitare i tentativi casuali accostando ai termini della successione S con quelli della successione T in cui, dato t₀ = 2, t_i+1 = f( f( t_i ) ).

Nell'esempio proposto:

Ovviamente l'insieme dei termini della successione T è un sottinsieme dell'insieme dei termini di S, quindi la differenza tra un termine di T e un termine di S è anche una differenza tra due termini di S. Accostando i termini delle due successioni e calcolando il massimo comun divisore tra n e il valore assoluto della differenza t_i - s_i, se il massimo comun divisore è maggiore di 1, esso è un divisore di n cioè h.

Si può quindi calcolare k = n / h.

1. n è espresso come prodotto di due numeri naturali h e k minori di n;
2. a loro volta h e k o sono primi o sono composti;
3. se sono entrambi primi, il loro prodotto è la scomposizione di n in prodotto di fattori primi;
4. in caso contrario si può applicare il crivello o il metodo di Fermat o l'algoritmo di Pollard ai fattori composti e ripetere il procedimento finché non si ottengono solo fattori primi;
5. se al termine del procedimento un fattore compare più volte il prodotto dei fattori identici è sostituito da una potenza e il prodotto di queste potenze (con esponente ≥ 1) è la scomposizione di n in prodotto di potenze di fattori primi.

9. Calcolatrice

La seguente applicazione Javascript esegue i calcoli descritti.
Ovviamente, perché essa funzioni a dovere il vostro browser deve abilitare Javascript.
Se il vostro browser non permette i frames interni, potete accedere direttamente alla pagina dell'applicazione.
Se il tempo di calcolo supera i minuti indicati, potete provare ad aumentarli.

9. Numeri molto grandi.

Le applicazioni di questa pagina sono redatte in JS e, per quanto potenziate dalla libreria BigInt di Leemon Baird, risultano inevitabilmente troppo lente per trattare numeri molto grandi. Dovendo scomporre in fattori numeri molto grandi si può ricorrere a WolframAlpha.

Va comunque osservato che, anche usando il software più evoluto e hardware appositamente progettato, la scomposizione in fattori di un numero molto grande può richiedere tempi di calcolo impraticabili e questo fatto è alla base dei metodi di crittografia più efficienti, come ad esempio la crittografia RSA.

ultima revisione: Giugno 2020