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 concettualmente 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 inizializza un array di n elementi tutti uguali a 0 tranne il primo posto uguale al primo numero primo 2; 0 è il codice per i numeri non ancora elaborati;
  2. partendo dal quadrato dell'ultimo primo p individuato si pongono a 1 gli elementi in posizione multipla di p; 1 è il codice per i numeri composti;
  3. il numero p' in posizione successiva a quella di p, dove deve stare il primo successivo, è provvisoriamente p+1;
  4. si controlla il numero in posizione p';
  5. se in questa posizione c'è 1, p' è composto e viene sostituito da suo successivo;
  6. si ripetono i passi 4 e 5 fino a che nella posizione p' c'è 0, cioè p' è primo;
  7. si riprende dal passo 2 e si cicla finché fino ad esaurire il campione di n numeri.

Una possibile implementazione in Javascript della procedura proposta, facilmente traducibile in altri linguaggi, può essere la seguente.

function crivello(n)
//array dei primi minori di n
  {
    var s = new Array(n); // se n è molto grande possono esserci problemi di memoria insufficiente
    var i;
    for (i=0; i<n; i++) s[i]=0; // tutti gli elementi di s sono 0;
    s[0] = 2; // il primo elemento di s è 2;
    var ix = 2, p = 0;
    while (ix<n) 
      {
        for (i = ix*ix; i<n; i+=ix)
          s[i]=1;  //le posizioni dei multipli di s[ix] sono messe a 1; questi elementi sono composti
        p++;
        s[p] = s[p-1]+1; // in s[p] è provvisoriamente il numero successivo all'ultimo primo registrato
        while(s[p]<n && s[s[p]])
          s[p]++; //fintanto che l'elemento in posizione s[p] è composto (quindi 1), sostituirlo con il numero successivo
        ix = s[p]; //ix: l'ultimo primo registrato
      }
    s.length = p; //si tronca l'array s al numero effettivo dei primi registrati
    return s;
  }

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.

 

 


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

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.

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

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

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.

 

 


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.

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.

 

 


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 Qn = {q1, q2, … qn } dei numeri primi minori della radice quadrata di n.
  2. 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.
  3. 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.

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

Siano h un divisore di n.

Se, dati s0 = a e la funzione f(s) = mod(s2+2,n), si costruisce la successione S in cui si+1 = f( si ), allora, dopo al massimo h+1 passaggi, si trova un ss tale che ss = sk (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 s0 = 2, si ha

isif( si )
026
1638
23818
31820
42045
54538
63818
71820
82045
94538

s2 = s6, quindi s3 = s7 e così via.

Se ij, sj > si e sjsi (mod h), si ha:

e quindi

MCD ( sj - si , n ) = h

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

263818204538182045
2043616184336161843
6403012143930121439
383632020187020187
181612200227200227
201814182025182025
454339727250727250
383630020187020187
181612200227200227
201814182025182025
454339727250727250

Quindi, scelti a caso si e sj con ij, MCD(di,j,n) > 1, allora MCD(di,j,n) = h.

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

Nell'esempio proposto:

isiti| ti - si |
0220
163832
2382018
3183820
420200
545387
6382018
7183820
820200
945387

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 ti - si, 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

 

 

 


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 03/05/2018