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.

Se i numeri primi non fossero infiniti, esisterebbe il massimo numero primo M e sarebbe possibile calcolare il numero P = 2·3·5·7·11·13·…·M, uguale al prodotto di tutti i numeri primi

Si consideri il numero naturale S immediatamente successivo a P: S=P+1.

È impossibile che S sia primo, perché maggiore del massimo primo M.

Dividendo S per qualunque numero primo, si otterrebbe come quoziente il prodotto dei rimanenti numeri primi e resto 1 e quindi S non è divisibile per nessuno dei numeri primi, quindi deve essere primo.

Si ottengono così due affermazioni contraddittorie. Bisogna pertanto ammettere che i numeri primi sono infiniti.

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

 


2. Il crivello di Eratostene

Il metodo più semplice per ottenere l'insieme Pn dei numeri primi ≤ n (n>13) è il crivello di Eratostene
(il crivello o vaglio o setaccio è un attrezzo per filtrare la farina separandola dalla crusca):

  1. si immettono immediatamente in Pn i numeri 2, 3, 5, 7;
  2. si forma l'insieme Dn di tutti i numeri dispari d: 7 < dn;
  3. si eliminano da Dn tutti i multipli di 3, 5, 7;
  4. il primo dei numeri rimasti in Dn è primo: lo si elimina da Dn e lo si immette in Pn;
  5. si eliminano da Dn tutti i multipli di questo numero;
  6. si ripetono i passi 4 e 5 finché Dn rimane vuoto;
  7. al termine della procedura Pn contiene tutti i primi cercati.

 

 

Per stabilire se un numero dispari n è primo, cioè per controllarne la primalità, si può costruire l'insieme Pn e controllare se nPn.

Questa procedura però è inutilmente dispendiosa in quanto un eventuale divisore di n non può superarne la radice quadrata. Conviene quindi:

  1. calcolare l'insieme Qn = {q1, q2, … qn } dei numeri primi minori della radice quadrata di n;
  2. calcolare il resto della divisione di n per ognuno degli elementi di Qn a partire dal primo;
  3. se si trova un resto uguale a 0, n non è primo e la procedura ha termine;
  4. altrimenti n è primo.

Anche con questo miglioramento, se n è molto grande, il crivello risulta impraticabile per il lungo tempo di calcolo richiesto. Sono stati quindi cercati e vengono cercati ancor oggi test di primalità diretti, cioè non richiedenti il calcolo di un numero enorme di primi.

 


3. Il metodo di fattorizzazione di Fermat

Un primo test diretto di primalità è 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

Eqn001.gif

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.

Se n non è troppo grande conviene applicare il crivello di Eratostene.

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

Eqn002.gif

quindi, posto

Eqn003.gif

si ha

Eqn004.gif

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

A questo scopo si procede per tentativi:

Ricavati a e b si ha

Eqn005.gif

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 Fermat prevede 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 quadratici modulo m, per un numero m prefissato, sono in numero abbastanza ridotto.

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

fig001.png

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 quadratici modulo 9.

fig002.png

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 qi che, iniziando da 4, è formata da numeri tali che ognuno di essi è il quadrato del precedente.

    Eqn006.gif

  2. Se n coincide con uno dei qi, n è un quadrato perfetto e la procedura finisce.
  3. Altrimenti neanche √n coincide con un qi ed è compresa tra due di questi termini:
    Eqn007.gif;
  4. Si pone
    Eqn008.gif
  5. Si confronta n con il quadrato del valor medio m tra min e max: Eqn009.gif

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 1Eqn010.gif
passo 2Eqn011.gif
passo 3Eqn012.gif
passo 4Eqn013.gif
passo 5Eqn014.gif
passo 6Eqn015.gif
passo 7Eqn016.gif
finen è un quadrato perfetto; la sua radice quadrata è 201

 


5. Scomposizione di un numero in prodotto di potenze di numeri primi.

Un numero naturale n o è primo o è composto. Se n è composto, con il metodo di Fermat n può essere espresso come prodotto di due numeri naturali h e k minori di n. A loro volta h e k o sono primi o sono composti. Se sono entrambi primi, il loro prodotto è la scomposizione di n in prodotto di fattori primi (o fattorizzazione di n). In caso contrario si può applicare il metodo di Fermat ai fattori composti e ripetere il procedimento finché non si ottengono solo fattori primi. 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, specialmente quando il numero n che si tenta di fattorizzare è un grande numero primo, per il quale i fattori h e k ricercati sono n stesso e 1, quindi molto distanti da √n.

In alternativa si potrebbe usare il crivello di Eratostene.

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

Tuttavia, se n è molto grande, anche √n è grande ed è grande anche il numero degli elementi di Qn il cui calcolo può richiedere tempi impraticabili, tanto più se n è primo, perché è necessario eseguire le divisioni di n per tutti i qi prima di giungere alla conclusione che n è primo.

Quindi, prima di tentare la fattorizzazione di un grande numero, conviene accertarsi con metodi più efficienti che n non sia un numero primo. Questi metodi in generale sono di tipo probabilistico, cioè tali da non produrre la certezza matematica della primalità di n, ma da garantirla con un grado di probabilità talmente alto da risultare pienamente affidabile in molte situazioni operative.

 


6. Il test di primalità di Fermat

Storicamente il primo di questi metodi è ancora dovuto a Fermat e si basa su un teorema enunciato da Fermat stesso, ma dimostrato successivamente da L. Euler, noto come Piccolo Teorema di Fermat.

Se p è primo, allora, per qualunque numero naturale n, Eqn017.gif

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

Ad esempio: dati n=10 e p=3, si ha:

Una dimostrazione del teorema si può ottenere per induzione.

Prima di tutto si osserva che, se p è primo,

Eqn018.gif

Infatti, sviluppando la potenza del binomio, si ha

Eqn019.gif

dove

Eqn020.gif

Ora si procede per induzione, osservando che il teorema vale per n=0 e n=1:

Eqn021.gif

Assumendo il teorema valido per n

Eqn022.gif

per la (1) si ha

Eqn023.gif

Quindi, per induzione, il teorema vale per ogni n.

In particolare, se n non ha divisori comuni con p, cioè è coprimo rispetto a p, si ha

Eqn024.gif

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 Eqn025.gif. 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.

Esempi.

1. Sia q=41.

Si hanno così tre indizi indipendenti sulla primalità di 41, che è effettivamente primo come si può facilmente verificare.

2. Sia q=91.

3. Sia q=561.

Applicando il metodo di fattorizzazione di Fermat si ottiene 561=17·33. Dunque 561 è composto.

Si prova ora ad applicare il test di Fermat.

 

 


5. 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.

Eqn026.gif

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

Eqn027.gif

da cui

Eqn028.gif

quindi

Eqn029.gif

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 nd≡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:

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.

Esempi.

1. Come si è visto il numero q=561, pur essendo composto, supera il test di Fermat.

Si scompone 560 in prodotto tra un numero dispari e una potenza di 2: 560=35·24

Con n=2, si ha 235=34359738368; 235≡ 263 (mod 561)

35·23=280;
2280=1942668892225729070919461906823518906642406839052139521251812409738904285205208498176
2280≡1 (mod 561)

35·22=140;
2140=1393796574908163946345982392040522594123776
2140≡67 (mod 561)

Dunque 561 è composto.

 

2. Sia q=601

Con n=2, si ha
2600=414951556888099295851240786369116115101244623224243689999565732969065281141290814639970704894710379428
8197886611300789182395151075411775307886874834113963687061181803401509523685376
2600≡1 (mod 601): si supera il test di Fermat.

600=75*23

Con n=2 si ha

275=37778931862957161709568; 275≡ 1 (mod 601): 601 è probabilmente primo.

 

3. Sia q=401

Con n=2, si ha
2400=2582249878086908589655919172003011874329705792829223512830659356540647622016841194629645353280137831435903171972747493376
2400≡1 (mod 401): si supera il test di Fermat.

400=25·24

Con n=2 si ha

225=33554432; 275≡356 (mod 401)

2200=1606938044258990275541962092341162602522202993782792835301376; 2200≡ 1 (mod 401);

2100=1267650600228229401496703205376; 2100≡ -1 (mod 401): 401 è probabilmente primo.

 

 


6. Calcolatrice

 

 

 


7. 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 26/06/2016