Come Riconoscere un Numero Primo

I numeri primi sono interi che possono essere divisi solo per se stessi o per 1. Tutti gli altri numeri vengono definiti "numeri composti" (cioè che hanno più divisori). Esistono numerosi metodi per testare la primalità di un numero intero, ognuno dei quali richiede un inevitabile compromesso iniziale e una gran mole di lavoro. Questo perché alcuni metodi di calcolo sono più adatti a numeri piccoli, risultando estremamente lenti per numeri di grandi dimensioni, mentre altri risultano essere molto veloci, ma purtroppo possono generare dei "falsi positivi" (cioè indicare un numero come primo quando invece è composto). In questo articolo vengono trattati diversi metodi per calcolare la primalità di un numero intero, la cui scelta dipende dalla dimensione del numero da controllare.

Parte 1

Parte 1 di 3:

Metodi per Verificare la Primalità di un Numero Intero

Scarica PDF

Nota: in tutte le formule che seguono, la variabile n indica il numero intero di cui si sta testando la primalità.

1
Metodo delle divisioni successive. Si tratta del metodo di verifica più semplice, in cui si divide n per ogni numero primo compreso fra 2 e la ( ${\sqrt {n}}$ ).
2
Test di Fermat. È un metodo di calcolo basato sul "piccolo Teorema di Fermat". Fai molta attenzione perché, in questo caso, è possibile ottenere dei "falsi positivi" anche per tutti i valori assunti dalla variabile "a".
- Scegli un numero intero per a compreso nell'insieme 2 ≤ a ≤ n - 1.
- Se aⁿ (mod n) = a (mod n), allora n è probabilmente un numero primo. Al contrario, se questa equazione non è vera, allora n è sicuramente un numero composto.
- Ripeti i passaggi precedenti per diversi valori di a, in modo da incrementare la probabilità che n sia un numero primo.
3
Test di Miller-Rabin. Anche in questo caso è possibile ottenere dei "falsi positivi", ma è un evento molto raro se si effettua il test con molteplici valori di a.
- Individua i valori assunti dalle variabili s e d, in modo che venga rispettata la seguente equazione $n-1=2^{s}*d$ .
- Scegli un numero intero per a compreso in questo insieme 2 ≤ a ≤ n - 1.
- A questo punto, se a^d = +1 (mod n) o a^d = -1 (mod n), allora n è probabilmente un numero primo. Adesso puoi scegliere di passare direttamente alla verifica del risultato ottenuto oppure di proseguire con il passaggio successivo.
- Calcola la radice quadrata della seguente espressione $a^{2d}$ . Se il risultato è uguale a +1 (mod n) o -1 (mod n), procedi a verificare la correttezza del test, altrimenti ripeti i calcoli usando le espressioni successive: $a^{4d}$ , $a^{6d}$ , eccetera, fino ad arrivare al valore $a^{2^{s-1}d}$ .
- Controlla il risultato ottenuto: se n ha superato il test, ripetilo utilizzando un valore diverso di a per aumentare le probabilità che sia effettivamente un numero primo.
Pubblicità

Parte 2

Parte 2 di 3:

Comprendere il Funzionamento dei Test di Primalità

Scarica PDF

1
Metodo delle divisioni successive. La definizione di un numero primo afferma che n può essere definito primo se non è divisibile interamente per 2 o per un intero più grande. La formula che viene fornita in questo passaggio ha il vantaggio di far risparmiare tempo, dato che scarta automaticamente le prove non necessarie (ad esempio, dopo aver testato il divisore 3 non è necessario eseguire la stessa operazione utilizzando il numero 9).
- Limita il valore di x arrotondandolo all'intero più vicino che sia maggiore o uguale a x.
2
Comprendi l'aritmetica modulare. L'operazione "x mod y" (nell'aritmetica modulare l'espressione "mod" è l'abbreviazione di "modulo") significa calcolare il "resto della divisione di x per y".^{[1]XFonte di ricerca} In altre parole, nell'ambito dell'aritmetica modulare, i numeri interi si "avvolgono su se stessi", cioè ripetono la successione iniziale da zero ogni volta che raggiungono i multipli di un determinato valore n, chiamato appunto modulo. È questo il caso dell'orologio che mostra l'ora in cicli continui di 12 o 24 ore (quindi in modulo 12 o 24). Infatti la sequenza di valori in esame è 1, 2, 3, 4, ...., 10, 11 e 12 per poi riprendere da 1 e così via.
- Molte calcolatrici sono dotate del tasto "mod", ma alla fine di questa sezione viene mostrato come è possibile svolgere i calcoli relativi a numeri di grandi dimensioni anche manualmente.
Ricorda che, in questo caso, tutti i numeri che non superano il test di Fermat sono sicuramente numeri "composti" (cioè non sono numeri primi), ma purtroppo i numeri che superano questa verifica hanno solo la probabilità di essere numeri primi. Se vuoi avere la certezza di non essere incappato in un "falso positivo", individua il numero n all'interno della lista dei "numeri di Carmichael" (che sono i numeri che hanno superato il test di Fermat per ogni valore assunto da a) o all'interno dei numeri "pseudoprimi di Fermat" (numeri che hanno superato il test solo per alcuni valori di a).^{[2]XFonte di ricerca}
Anche se si tratta di un metodo molto lungo da applicare manualmente, questo algoritmo viene spesso usato all'interno di software. Si tratta di un metodo di calcolo veloce, che restituisce un numero inferiore di "falsi positivi" rispetto al test di Fermat.^{[3]XFonte di ricerca} Un numero "composto" non restituisce mai un "falso positivo" per più di un quarto dei valori assunti da a.^{[4]XFonte di ricerca} Se si scelgono in modo casuale diversi valori di a, che sono tutti in grado di superare il test, allora è molto probabile che il numero n esaminato sia un numero primo.
5
Utilizza l'aritmetica modulare nel caso di un numero di grandi dimensioni. Se non hai a portata di mano una calcolatrice dotata della funzione "mod" o se quella in tuo possesso non è in grado di gestire numeri di grandi dimensioni, usa le proprietà delle potenze e l'aritmetica modulare per semplificare il processo e poter eseguire i calcoli anche manualmente.^{[5]XFonte di ricerca} Ecco un esempio di come calcolare la seguente operazione $3^{50}$ $How.com.vn Italiano: 3^{{50}}$ mod 50:
- Riscrivi l'espressione di partenza in modo che risulti più semplice ottenendo $(3^{25}\times 3^{25})$ mod 50 (se stai eseguendo i calcoli a mano, molto probabilmente dovrai semplificarla ulteriormente).
- $(3^{25}\times 3^{25})$ mod 50 = $(3^{25}$ mod 50 $\times 3^{25}$ mod 50) mod 50 (questa è una delle proprietà della moltiplicazione modulare).
- $3^{25}$ mod 50 = 43
- $(3^{25}$ mod 50 $\times 3^{25}$ mod 50) mod 50 = $(43\times 43)$ mod 50
- $=1849$ mod 50
- $=49$
Pubblicità

Parte 3

Parte 3 di 3:

Teorema Cinese del Resto

Scarica PDF

1
Scegli due numeri. Uno dei due interi scelti è un numero composto (cioè non primo), mentre il secondo è il numero di cui si vuole testare la primalità.
- "Numero_1" = 35
- "Numero_2" = 97
2
Adesso scegli due valori maggiori di zero e diversi fra loro ma entrambi inferiori al valore assunto dalle variabili "Numero_1" e "Numero_2".
- Valore_1 = 1
- Valore_2 = 2
3
A questo punto, calcola l'inverso moltiplicativo del "Numero_1" e del "Numero_2".
- Calcolo dell'Inverso Moltiplicativo (IM)
  - IM_1 = Numero_2 ^ -1 mod Numero_1
  - IM_2 = Numero_1 ^ -1 mod Numero_2
- Da usare solo nel caso di numeri primi (questo metodo, nel caso di numeri composti, dà come risultato un valore che non è l'inverso moltiplicativo degli interi di partenza):
  - IM_1 = (Numero_2 ^ (Numero_1-2)) mod Numero_1
  - IM_2 = (Numero_1 ^ (Numero_2-2)) mod Numero_2
- Nel nostro esempio otterremo:
  - IM_1 = (97 ^ 33) % 35
  - IM_2 = (35 ^ 95) % 97
4
Crea una tabella binaria per ogni inverso moltiplicativo che abbia come limite il logaritmo in base 2 del modulo.
- Inverso moltiplicativo IM_1
  - F(1) = Numero_2 mod Numero_1 = 97 % 35 = 27
  - F(2) = F(1) * F(1) mod Numero_1 = 27 * 27 % 35 = 29
  - F(4) = F(2) * F(2) mod Numero_1 = 29 * 29 % 35 = 1
  - F(8) = F(4) * F(4) mod Numero_1 = 1 * 1 % 35 = 1
  - F(16) =F(8) * F(8) mod Numero_1 = 1 * 1 % 35 = 1
  - F(32) =F(16) * F(16) mod Numero_1 = 1 * 1 % 35 = 1
- Calcola il corrispondente binario dell'espressione (Numero_1 - 2)
  - 35 - 2 = 33 = (10001) in base 2
  - IM_1 = F(33) = F(32) * F(1) mod 35
  - IM_1 = F(33) = 1 * 27 % 35
  - IM_1 = 27
- Inverso moltiplicativo IM_2
  - F(1) = Numero_1 mod Numero_2 = 35 % 97 = 35
  - F(2) = F(1) * F(1) mod Numero_2 = 35 * 35 % 97 = 61
  - F(4) = F(2) * F(2) mod Numero_2 = 61 * 61 % 97 = 35
  - F(8) = F(4) * F(4) mod Numero_2 = 35 * 35 % 97 = 61
  - F(16) = F(8) * F(8) mod Numero_2 = 61 * 61 % 97 = 35
  - F(32) = F(16) * F(16) mod Numero_2 = 35 * 35 % 97 = 61
  - F(64) = F(32) * F(32) mod Numero_2 = 61 * 61 % 97 = 35
  - F(128) = F(64) * F(64) mod Numero_2 = 35 * 35 % 97 = 61
- Calcola il corrispondente binario dell'espressione (Numero_2 - 2)
  - 97 - 2 = 95 = (1011111) in base 2
  - IM_2 = (((((F(64) * F(16) mod 97) * F(8) mod 97) * F(4) mod 97) * F(2) mod 97) * F(1) mod 97)
  - IM_2 = (((((35 * 35) % 97) * 61) % 97) * 35 % 97) * 61 % 97) * 35 % 97)
  - IM_2 = 61
5
Calcola la seguente espressione (Valore_1 * Numero_2 * IM_1 + Valore_2 * Numero_1 * IM_2) mod (Numero_1 * Numero_2). Nel nostro esempio otterremo:
- Risultato_finale = (1 * 97 * 27 + 2 * 35 * 61) % (97 * 35)
- Risultato_finale = (2.619 + 4.270) % 3.395
- Risultato_finale = 99
6
Controlla che il "Numero_1" non sia un numero primo.
- Esegui il seguente calcolo (Risultato_finale - Valore_1) mod Prime1.
- Dopo la sostituzione delle variabile con i rispettivi valori, otterremo 99 -1 % 35 = 28.
- Dato che 28 è maggiore di 0, allora 35 è un numero composto.
7
Controlla se il Numero_2 è un numero primo.
- Esegui il seguente calcolo (Risultato_finale - Valore_2) mod Prime2.
- Dopo la sostituzione delle variabile con i rispettivi valori, otterremo 99 - 2 % 97 = 0.
- Dato che l'equazione 0 = 0 è sempre vera, significa che 97 è potenzialmente un numero primo.
8
Ripeti i passaggi dal numero 1 al numero 7 per almeno altre due volte.
- Se il passaggio numero 7 dà come risultato 0, esegui altri test basandoti sulle seguenti indicazioni:
  - Scegli un valore della variabile "Numero_1" che sia diverso dal precedente e che non sia un numero primo.
  - Scegli un valore della variabile "Numero_1" che sia diverso dal precedente, ma che questa volta sia effettivamente un numero primo. In questo caso, il risultato dei passaggi 6 e 7 dovrebbe essere pari a zero.
  - Scegli due valori diversi per le variabili "Valore_1" e "Valore_2".
- Se il risultato del passaggio numero 7 è sempre pari a zero, significa che la probabilità che il "Numero_2" scelto sia primo è altissima.
- Ricorda che è noto che la serie di calcoli indicati nei passaggi dal numero 1 al numero 7 diano un risultato sbagliato in alcuni casi specifici. Ad esempio, quando la variabile "Numero_1" non rappresenta un numero primo e la variabile "Numero_2" è un fattore del valore assunto dalla variabile "Numero_1". Al contrario, questo metodo funziona perfettamente in tutti gli scenari in cui entrambi i numeri scelti ("Numero_1" e "Numero_2") sono numeri interi primi.
- Il motivo per cui è necessario ripetere più volte i calcoli descritti nei passaggi dal numero 1 al numero 7 risiede nel fatto che esistono alcuni scenari in cui, anche se il "Numero_1" non è un numero primo così come il "Numero_2", il risultato ottenuto dal passaggio numero 7, relativamente a uno dei due numeri testati o a entrambi, è comunque pari a zero. Si tratta di una circostanza che si verifica molto raramente. Scegliendo un diverso numero composto da assegnare alla variabile "Numero_1", se il "Numero_2" non è un numero primo, il risultato che si ottiene nel passaggio numero 7 sarà subito diverso da zero. Ad eccezione dello scenario in cui l'intero scelto per la variabile "Numero_1" è un fattore del valore scelto per la variabile "Numero_2", questo test darà sempre zero come risultato finale se il numero esaminato è effettivamente un numero primo.
Pubblicità

Consigli

Questo è l'elenco completo dei 168 numeri primi minori di 1.000: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997^{[6]XFonte di ricerca}.
Anche se il metodo delle divisioni successive risulta più lento rispetto ad altri metodi più sofisticati nell'individuare se un numero di grandi dimensioni è primo, risulta comunque abbastanza efficiente nel caso di numero piccoli. Tuttavia, non è inconsueto usare questo metodo per testare la primalità di numeri grandi, partendo dalla ricerca dei fattori più piccoli, per poi passare a utilizzare metodi più avanzati, nel caso in cui questi ultimi non siano presenti.