Test di primalità probabilistico

Un test di primalità probabilistico è un algoritmo che verifica se un numero è primo tramite dei controlli basati su scelte casuali.

I test probabilistici forniscono una risposta certa solo se il numero è composto. Viceversa, possono solo affermare con una probabilità più o meno alta che un numero è primo.

Si distinguono dai test deterministici che, invece, restituiscono un risultato certo in entrambi i casi,

Nota. La probabilità di errore può essere ridotta aumentando il numero di iterazioni, rendendo il test molto affidabile ed efficiente rispetto ai metodi deterministici.

Come funziona
Un esempio pratico
Qual è la probabilità che un numero sia primo?

Come funziona

Esistono diverse tipologie di test di primalità probabilistici e, per chiarire il concetto, mi riferirò al più semplice di tutti.

L'algoritmo funziona in questo modo.

Devo capire se il numero $ n $ è primo oppure no.
Scelgo a caso un numero intero $ a $ compreso nell'intervallo $$ 1 < a < n $$
Calcolo il massimo comune divisore tra $ n $ e $ a )
- Se il $ MCD(n,a)>1 $ è maggiore di 1, allora i due numeri hanno un divisore in comune. Pertanto, è certo che \( n $ non è primo e l'algoritmo finisce qua.
- Se il $ MCD(n,a)=1 $ è uguale a 1, allora i due numeri non hanno un divisore in comune, ossia sono coprimi. In questo caso devo verificare se $ n $ è pseudoprimo con la base $ a $ oppure no.
Verifico se $ n $ è pseudoprimo con la base $ a $ tramite il teorema di Fermat.
- Se $ a^{n-1} \not\equiv 1 \mod n $ il numero $ n $ non è pseudoprimo con $ a $. Pertanto, è certo che $ n $ non è primo e l'algoritmo termina.
- Se $ a^{n-1} \equiv 1 \mod n $ il numero $ n $ è pseudoprimo con $ a $. Il numero $ n $ probabilmente è primo.
Spiegazione. Il piccolo teorema di Fermat vale per tutti i numeri primi: \[ a^{n-1} \equiv 1 \mod n \] Se un numero non soddisfa questa relazione, allora è certamente composto. Tuttavia, il fatto che superi il test non garantisce che sia primo, poiché potrebbe trattarsi di un numero pseudoprimo.
L'algoritmo torna al punto 2 dove devo scegliere un altro numero $ a $ nell'intervallo $ 1<a<n $ diverso da quelli già testati.

Più iterazioni vengono effettuate dall'algoritmo, maggiore è la probabilità che il numero sia primo. Tuttavia, non è mai possibile affermarlo con assoluta certezza.

Al contrario, se l'algoritmo determina che il numero è composto, il risultato è certo.

Nota. Se $ n $ è composto, c'è una probabilità significativa che venga individuato come tale già nei primi test. Se $ n $ supera molti test, è molto probabile che sia primo, ma non c'è certezza assoluta. La probabilità che un numero composto superi tutti i test si riduce esponenzialmente con il numero delle iterazioni e questo rende il test molto affidabile.

Questo algoritmo è molto semplice ma è utile per spiegare il funzionamento di base dei test di primalità probabilistici. Va però detto che esistono altri test probabilistici più affidabili.

Ad esempio, questo tipo di test è alla base di algoritmi celebri come il test di Miller-Rabin, utilizzato in crittografia per testare la primalità di numeri molto grandi.

Quali sono i vantaggi?

Un test di primalità probabilistico è molto più veloce di un test deterministico come il Crivello di Eratostene o il Test di Wilson. Inoltre, è efficace per numeri grandi, come quelli usati in crittografia.

E gli svantaggi?

Il risultato del test è sempre probabilistico: non può mai affermare con certezza assoluta che un numero sia primo, ma solo che è "probabilmente" primo.

Un esempio pratico

Utilizzo il test probabilistico per verificare la primalità di $ n = 91 $.

Prima iterazione

Scelgo a caso un numero intero $ a = 5 $ nell'intervallo $ 1 < 5 < 91 $.

Calcolo il massimo comune divisore tra 5 e 91

$$ MCD(5, 91) = 1 $$

Poiché il massimo comune divisore è 1, proseguo con il controllo di pseudoprimalità.

Verifico se 91 è pseudoprimo in base 5, ovvero se soddisfa la condizione di Fermat:

$$ 5^{90} \equiv 1 \pmod{91} $$

Calcolo la congruenza

\[ 5^{90} \mod 91 \]

Per svolgere il calcolo utilizzo la riduzione modulare iterativa:

$ 5^2 = 5 \cdot 5 = 25 \mod 91 $
$ 5^4 = 25 \cdot 25 = 624 \equiv 76 \mod 91 $
$ 5^8 = 76 \cdot 76 = 5776 \equiv 37 \pmod{91} $
$ 5^{16} = 37 \cdot 37 = 1369 \equiv 4 \pmod{91} $
$ 5^{32} = 4 \cdot = 16 \pmod{91} $
$ 5^{64} = 16 \cdot 16 = 256 \equiv 73 \pmod{91} $

Infine, moltiplicando i risultati parziali:

\[ 5^{90} = 5^{64} \cdot 5^{16} \cdot 5^8 \cdot 5^2 \pmod{91} \]

\[ 5^{90} = 73 \cdot 4 \cdot 37 \cdot 25 \equiv 1 \pmod{91} \]

\[ 5^{90} \equiv 1 \pmod{91} \]

Quindi $ 91 $ è pseudoprimo in base 5, per cui non posso affermare nulla. E' necessario svolgere un altro test.

Seconda iterazione

Scelgo un altro numero a caso $ 1 < a < 91 $ diverso dal precedente. Ad esempio $ a=2 $

Il massimo comune divisore tra $ n=91 $ e $ a =2 $ è sempre 1.

$$ MCD(91,2) = 1 $$

Quindi, effettuo il test di pseudoprimalità $ a^{n-1} \equiv 1 \pmod{n} $ tra $ n=91 $ e $ a =2 $

\[ 5^{90} \equiv 1 \pmod{91} \]

Anche in questo caso, il numero $ n=91 $ è pseudoprimo con $ a=2 $. Quindi, devo svolgere altre iterazioni.

Terza iterazione

In questa iterazione scelgo $ a = 7 $.

Calcolo il massimo comune divisore tra 7 e 91.

\[ \gcd(7, 91) = 7 \]

Poiché il massimo comune divisore è maggiore di 1, concludo immediatamente che 91 è un numero composto. Quindi, non è un numero primo.

Il risultato è certo perché il test probabilistico di primalità è fallito.

Nota. Questo esempio mostra come si possa verificare rapidamente che $ 91 $ non è primo dopo appena poche iterazioni, grazie al calcolo del massimo comune divisore. Ovviamente tutto dipende dalla probabilità di giungere a un risultato certo. Ad esempio, nel caso di numeri con fattori primi grandi o meno frequenti, il test potrebbe richiedere più iterazioni prima di fornire una certezza.

Qual è la probabilità che un numero sia primo?

Quando il test probabilistico afferma che un numero $ n $ è primo, il risultato non è mai certo.

La probabilità che il test restituisca un risultato vero sulla primalità del numero $ n $ dipende dalla grandezza del numero e dal numero dei suoi fattori primi.

Inoltre, la probabilità è maggiore se i fattori primi del numero $ n $ sono molto piccoli (es. 2, 3, 5, ecc.).

Esempio 1

La probabilità di rilevare che $ n = 91 $ è composto al primo tentativo (iterazione) dipende dalla scelta casuale del numero $ a $ e dal valore di $ MCD(a, 91) $.

La fattorizzazione di 91 è

$$ 91 = 7 \times 13 $$

Quindi, un numero $ a $ farà concludere immediatamente che $ 91 $ è composto se $ MCD(a, 91) > 1 $, ovvero se $ a $ è un multiplo di 7 o 13.

Quanti numeri posso scegliere?

Scegliendo $ a $ in modo casuale tra $ 1 < a < 91 $, cioè tra i numeri interi da 2 a 90. Il numero di scelte possibili è 89:

\[ 90 - 1 = 89 \]

I numeri multipli di 7 minori di 91 sono 12 valori:

\[ 7, 14, 21, 28, 35, 42, 49, 56, 63, 70, 77, 84 \]

I numeri multipli di 13 minori di 91 sono 6 valori:

\[ 13, 26, 39, 52, 65, 78 \]

Complessivamente, i multipli dei fattori primi sono $ 12+6 = 18 $ numeri interi su $ 89 $ disponibili.

Nota. Bisogna fare attenzione al doppio conteggio, può capitare che un multiplo di un numero sia anche multiplo dell'altro. In questo caso, va contato una sola volta. In questo esempio non si è verificato questa situazione ma va tenuta in seria considerazione.

Quindi, la probabilità di scegliere un valore $ a $ che rilevi subito che $ 91 $ è composto è circa 20,2%:

\[ \frac{12 + 6}{89} = \frac{18}{89} \approx 0.202 \]

Man mano che procedo con le iterazioni, la probabilità aumenta leggermente, poiché il numero di basi possibili si riduce: i valori $ a $ già scelti non devono essere ricontrollati.

Ad esempio, alla seconda iterazione rimangono 18 possibilità su 88 (circa il 20,4% di probabilità), mentre alla terza iterazione si considerano 18 possibilità su 87 (circa il 20,6% di probabilità) e via dicendo.

Esempio 2

In questo esempio calcolo la probabilità di individuare al primo colpo che $ n = 819 $ è un numero composto.

I fattori primi di $ 819 $ sono tre:

\[ 819 = 3^2 \times 7 \times 13 \]

Quindi $ 819 $ è divisibile per $ 3, 7 $ e $ 13 $.

Un numero $ a $ scelto casualmente tra $ 1 < a < 819 $ permetterà di rilevare subito la composizione di $ 819 $ se è multiplo di 3, 7 o 13.

Complessivamente, i numeri interi tra cui posso scegliere casualmente sono $ 818 - 1 = 817 $.

I multipli di 3, 7 e 14 minori di 819 sono 387.

Nota. Anche in questo caso devo fare attenzione al doppio conteggio. Ad esempio, tra 1 e 819 il fattore 3 ha 272 multipli, il fattore 7 ne ha 116 e il fattore 13 ne ha 62. $$ 272 + 116+ 13 = 401 $$ Tuttavia ci sono molti fattori duplicati come 21 che è multiplo sia di 3 che di 7, 39 è multiplo sia di 13 che di 3, ecc. Questi multipli vanno contati una sola volta. Per questa ragione i multipli da scartare sono 387 e non 401.

A questo punto ho tutte le informazioni per calcolare la probabilità.

La probabilità di individuare al primo colpo che $ 819 $ è un numero composto è circa del 47%,

\[P = \frac{387}{817} \approx 0.474\]

La probabilità è molto più alta rispetto all'esempio precedente, per $ 91 $ che del 20,2%, perché il numero $ 819 $ ha $ 3 $ fattori primi mentre il numero $ 91 $ solo due.

Inoltre, tra i fattori primi di $ 819 $ c'è un fattore molto piccolo, ossia $ 3 $, che ha molti multipli tra 1 e 819.

Conclusione

La probabilità di trovare un risultato certo dipende dalla struttura dei fattori primi del numero:

Se $ n $ ha molti fattori primi la probabilità aumenta.
Se $ n $ ha piccoli fattori primi molto frequenti (es. 2, 3, 5), la probabilità aumenta.
Se $ n $ ha fattori primi grandi e meno comuni, la probabilità diminuisce.

Per numeri molto grandi con fattori primi grandi e rari, può essere necessario testare più valori di $ a $ prima di concludere che $ n $ è composto.

E così via.