Test probabilistico di primalità di Solovay-Strassen

Il test probabilistico di primalità di Solovay-Strassen è un test che verifica se un numero $ n $ è primo con un metodo probabilistico basato sul criterio di Eulero, che afferma che se $ n $ è primo, allora per ogni intero $ b $ coprimo con $ n $ \[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \mod n \] Dove $ \left( \frac{b}{n} \right) $ è il simbolo di Legendre, che indica se $ b $ è un residuo quadratico modulo $ n $. Se un numero $ n $ non soddisfa questa congruenza per un certo $ b $, allora $ n $ non è primo.

Questo test non garantisce certezza assoluta, ma se un numero non è primo, il test lo rileva con alta probabilità.

Il test di Solovay-Strassen può dare falsi positivi, ossia numeri composti che passano il test ma non sono primi, chiamati pseudoprimi di Eulero.

Ciò nonostante, se reiterato molte volte il test è abbastanza affidabile e richiede poche risorse computazionali.

Qual è la probabilità di errore?

Se $ n $ è composto, la probabilità di non rilevarlo (falso positivo) è al massimo $ 1/2 $ per ogni iterazione.

Quindi, dopo $ k $ iterazioni, la probabilità di errore è al massimo $ 1/2^k $.

Differenze con il test di Miller-Rabin. Entrambi sono test di primalità probabilistici. Il test Solovay-Strassen è più teorico e meno usato, perché è più suscettibile ai falsi positivi, in quanto si basa sugli pseudoprimi di Eulero. Il test di Miller-Rabin è generalmente più affidabile e veloce nel rilevare i numeri composti perché gli pseudoprimi di Fermat forti sono molto più rari. Quindi, il test Miller-Rabin è la scelta standard nei test di primalità per numeri grandi, specialmente in crittografia e negli algoritmi RSA, mentre il test di Solovay-Strassen è superato.

Come funziona
Un esempio pratico

Come funziona

Devo verificare se un numero $ n $ è primo oppure no.

Scelgo a caso un numero $ b $ tale che $ 1 < b < n $
Verifico il massimo comune divisore tra $ n $ e $ b $ per capire se sono coprimi.
- Se $ \text{MCD}(b, n) > 1 $, allora $ n $ non è primo e l'algoritmo finisce qui
- Se $ \text{MCD}(b, n) = 1 $, l'algoritmo procede al passo successivo
Verifico se il test di Eulero $ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \mod n $ è soddisfatto tra $ n $ e $ b $
- Se la congruenza non è verificata, $ n $ non è primo e l'algoritmo finisce qui.
- Se la congruenza è verificata, $ n $ e $ b $ hanno passato il test e sono pseudoprimi di Eulero. Tuttavia, non posso affermare nulla sulla primalità di $ n $.

Il processo deve essere reiterato diverse volte per essere affidabile. Se il numero $ n $ passa il test per diversi valori casuali di $ b $, allora è probabilmente primo.

Se invece fallisce il test per almeno un valore $ b $, allora $ n $ è sicuramente un numero composto.

Un esempio pratico

Faccio un esempio concreto del test di primalità di Solovay-Strassen per verificare se $ n = 91 $ è primo.

Scelgo un numero casuale nell'intervallo $ 1<b<91 $. Ad esempo, il numero $ b = 10 $

Si tratta di un numero coprimo con $ n=91 $ perché il massimo comune divisore tra i due numeri è uguale a 1.

\[ \text{MCD}(10, 91) = 1 \]

Quindi, procedo al passo successivo e calcolo.

\[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \mod n \]

\[ 10^{(91-1)/2} \equiv \left( \frac{10}{91} \right) \mod 91 \]

\[ 10^{45} \equiv \left( \frac{10}{91} \right) \mod 91 \]

Il test mi richiede di calcolare $ 10^{45} \mod 91 $ nel lato sinistro.

$$ 10^{45} \equiv 1 \mod 91 $$

In questo caso la congruenza è uguale a 1.

Spiegazione. Questa congruenza modulare la posso calcolare usando il metodo delle potenze modulari. Ecco il calcolo passo dopo passo. Per prima cosa ottengo le potenze modulare in base 10 raddoppiando l'esponente a partire da 2.

$ 10^2 \equiv 9 \mod 91 $
$ 10^4 = (10^2)^2 = 9^2 \equiv 81 \mod 91 $
$ 10^8 = (10^4)^2 = 81^2 \equiv 10 \mod 91 $
$ 10^{16} = (10^8)^2 = 10^2 \equiv 9 \mod 91 $
$ 10^{32} = (10^{16})^2 = 9^2 = 81 \mod 91 $

Poi, usando questi dati, scompongo $ 10^{45} $ usando le proprietà delle potenze.

$$ 10^{45} = 10^{32} \cdot 10^8 \cdot 10^4 \cdot 10 = 81 \cdot 10 \cdot 81 \cdot 10 \mod 91 $$

$$ 22^{45} = 81^2 \cdot 10^2 = 10 \cdot 9 = 90 \mod 91 $$

$$ 22^{45} = 90 \mod 91 $$

Sostituisco $ 10^{45} $ con $ 90 $ nel test

\[ 10^{45} = 90 \equiv \left( \frac{10}{91} \right) \mod 91 \]

A questo punto è inutile calcolare anche il simbolo di Legendre / Jacobi $ \left( \frac{22}{91} \right) $ nel lato destro dell'equazione, perché so già che quest'ultimo può assumere soltanto i valori ± 1 che sono entrambi diversi da 90.

\[ 90 \not \equiv \pm 1 \mod 91 \]

Poiché i risultati non coincidono, posso affermare con certezza che il numero 91 non è primo. E' un numero composto.

Nota. Se il test avesse restituito una uguaglianza tra $ 22^{(n-1)/2} \mod n $ e il simbolo di Jacobi $ \left( \frac{22}{91} \right) $, allora non avrei potuto concludere che $ n $ fosse composto. In tal caso, avrei dovuto ripetere il test scegliendo altre basi $ b $, per ridurre la probabilità di errore. Infatti, se $ n $ è composto, la probabilità che un singolo test non lo rilevi è al massimo $ 1/2 $. Dopo $ k $ iterazioni indipendenti, la probabilità che $ n $ passi sempre il test è al massimo: \[ \frac{1}{2^k} \] Quindi, aumentando il numero di iterazioni con basi diverse, posso rendere arbitrariamente bassa la probabilità di errore, rendendo il test affidabile. Se invece, in una di queste iterazioni, il test fallisce (cioè i valori non coincidono), allora $ n $ è sicuramente composto, e non serve più continuare il test.

E così via.