I test di primalità
Cosa sono i test di primalità
I test di primalità sono test che permettono di capire se un numero intero è un numero primo oppure no.
Esistono due tipologie di test per verificare la primalità di un numero.
- Test deterministici: Forniscono una risposta certa sulla primalità di un numero, ma spesso risultano computazionalmente onerosi (es. crivello di Eratostene, test basati sul Teorema di Wilson).
- Test probabilistici: Si basano su una successione di test con probabilità d'errore decrescente. Se un numero non supera un test, è sicuramente composto. Se lo supera, c'è una piccola probabilità che sia composto, ma questa può essere ridotta aumentando il numero di test eseguiti.
L'idea chiave è che i test probabilistici, pur non garantendo assoluta certezza, possono fornire un'indicazione molto affidabile con un costo computazionale significativamente inferiore rispetto ai test deterministici.
Algoritmo di verifica della primalità con il limite della radice quadrata
Per verificare se un numero $ n $ è primo:
- Calcolo tutti i numeri primi fino a \( \sqrt{n} \) utilizzando un metodo come il crivello di Eratostene o una lista predefinita.
- Controllo se \( n \) è divisibile senza resto da uno qualsiasi dei numeri primi trovati nel passaggio precedente.
- Se nessuno dei numeri primi divide \( n \), allora \( n \) è primo.
Questo algoritmo consiste nel verificare se un numero $ n $ ha dei numeri primi come potenziali divisori.
Si basa sul fatto che un numero composto ha almeno un divisore primo minore o uguale alla sua radice quadrata.
Esempio
Devo verificare se il numero \( n = 29 \) è un numero primo.
$$ n = 29 $$
La radice quadrata di 29 è:
$$ \sqrt{29} \approx 5.38 $$
Genero la lista dei numeri primi fino a \( \sqrt{29} \approx 5.38 \):
$$ 2, 3, 5 $$
Verifico se uno dei numeri primi divide senza resto il numero \( n = 29 \)
$$ 29 : 2 = 14 \ \ r = 1 $$
$$ 29 : 3 = 9 \ \ r = 2 $$
$$ 29 : 5 = 5 \ \ r = 4 $$
Poiché nessuno di questi numeri primi divide \( n = 29 \) con resto zero ( \( r = 0 \) ), posso dedurre che 29 è un numero primo.
Nota. Questo algoritmo è molto semplice da utilizzare ed è abbastanza efficiente perché limita il controllo ai soli numeri primi fino a \( \sqrt{n} \). Inoltre, questo approccio è particolarmente utile per numeri grandi, poiché evita controlli inutili su numeri non primi.
Perché è sufficiente verificare la divisibilità solo numeri primi entro \( \sqrt{n} \)?
Se un numero \( n \) non è primo, allora deve esistere almeno un divisore \( d \) tale che \( 1 < d < n \).
Questo divisore \( d \) ha un complemento \( d' = n / d \) che è anch'esso un divisore di $ n $.
Ad esempio, il numero $ n = 36 $ è divisibile per $ d=2 $ che ha come complemento $ d'=18 $ perché $ 2 \times 18 = 36 $
Per evitare duplicazioni, posso ordinare \( d \) e \( d' \) come \( d \leq \sqrt{n} \) e \( d' \geq \sqrt{n} \).
Quindi, se \( n \) ha un divisore \( d > \sqrt{n} \), allora il complemento \( d' \) deve essere \( d' < \sqrt{n} \).
Questo significa che, per rilevare un divisore di \( n \), è sufficiente controllare la divisibilità con i numeri primi entro \( \sqrt{n} \).
Ad esempio, i divisori propri del numero \( n = 36 \) sono: 2, 3, 4, 6, 9, 12, 18.
- 2 divide 36 (2 × 18)
- 3 divide 36 (3 × 12)
- 4 divide 36 (4 × 9)
- 6 divide 36 (6 × 6)
Non serve andare oltre \( \sqrt{36} = 6 \) perché i restanti numeri 9, 12, 18 sono già stati considerati nei risultati precedenti: (2 × 18), (3 × 12), (4 × 9).
Pertanto, per verificare se \( n = 36 \) è un numero primo, basta controllare la divisibilità di \( n = 36 \) per i numeri primi fino alla radice quadrata \( \sqrt{36} = 6 \) ovvero per 2, 3 e 5.
$$ 36:2 = 18 \ \ r = 0 $$
In questo caso \( 36 \) è divisibile per 2 con resto zero, quindi non è un numero primo.
Il piccolo teorema di Fermat
Secondo il piccolo teorema di Fermat se p è un numero primo è sempre soddisfatta la congruenza $$ k^p \equiv k \mod p $$ per qualsiasi numero intero k.
Questo test restituisce due risultati:
- Se un numero \( n \) non soddisfa il piccolo teorema di Fermat, allora non è un numero primo.
- Se, invece, soddisfa il teorema, potrebbe essere un numero primo, ma non è possibile affermarlo con certezza. Potrebbe anche essere un numero pseudoprimo.
Esempio 1
Devo verificare se p=7 è un numero primo.
$$ k^7 \equiv k \mod 7 $$
Se p è un numero primo, allora qualsiasi numero intero k soddisfa la congruenza.
$$ 2^7 \equiv 2 \mod 7 \\ 128 \equiv 2 \mod 7 \\ 2 \equiv 2 \mod 7 $$
$$ 3^7 \equiv 3 \mod 7 \\ 2187 \equiv 3 \mod 7 \\ 3 \equiv 3 \mod 7 \\ \\ \vdots $$
Per qualsiasi intero k, la congruenza è soddisfatta. Pertanto p=7 è un numero primo.
Esempio 2
Ora verifico se p=9 è un numero primo
$$ k^9 \equiv k \mod 9 $$
Provo con k=2
$$ 2^9 \equiv 2 \mod 9 \\ 512 \equiv 2 \mod 9 \\ 8 \equiv 2 \mod 9 $$
In questo caso la congruenza non è soddisfatta per k=2. E' inutile procedere con altri tentativi.
Pertanto, l'intero p=9 non è un numero primo.
I limiti del piccolo teorema di Fermat
Il piccolo teorema di Fermat non è un test definitivo di primalità, perché esistono numeri composti che soddisfano questa relazione per alcuni (o anche per tutti) valori di \( a \).
Questi numeri sono detti pseudoprimi di Fermat.
Esempio
Considero il numero
$$ n = 561 $$
Il numero \( 561 \) è composto dai seguenti fattori primi
$$ 561 = 3 \cdot 11 \cdot 17 $$
Quindi, non è un numero primo.
Tuttavia, utilizzando il piccolo teorema di Fermat il numero \( 561 \) risulta erroneamente primo.
$$ k^{561} \equiv k \mod 561 $$
Provo con k=2 e l'equivalenza è soddisfatta.
$$ 2^{561} \equiv 2 \mod 561 $$
Nota. Secondo il teorema cinese dei resti quando un numero $ n $ è il prodotto di fattori coprimi, ovvero di numeri il cui MCD è 1, se una congruenza è valida modulo ciascun fattore primo, allora è valida anche modulo il loro prodotto. In questo caso il numero 561 è il prodotto di 3, 11, 17. Quindi, posso suddividere il problema in tre equivalenze. $$ 2^{561} \equiv 2 \mod 3 $$ $$ 2^{561} \equiv 2 \mod 11 $$ $$ 2^{561} \equiv 2 \mod 17 $$ Verifico se la prima è soddisfatta, sapendo che $ 2^2 \mod 3 = 1 $ $$ 2^{561} = (2^2)^{280} \cdot 2 \equiv 1^{280} \cdot 2 \equiv 2 \mod 3 $$ Verifico se la seconda è soddisfatta, sapendo che $ 2^{10} \mod 11 = 1 $ $$ 2^{561} = (2^{10})^{56} \cdot 2 \equiv 1^{56} \cdot 2 \equiv 2 \mod 11 $$ Verifico se la terza è soddisfatta, sapendo che $ 2^{16} \mod 17 = 1 $ $$ 2^{561} = (2^{16})^{35} \cdot 2 \equiv 1^{35} \cdot 2 \equiv 2 \mod 17 $$ Le tre equivalenze sono soddisfatte, pertanto lo è anche l'equivalenza $$ 2^{561} \equiv 2 \mod 561 $$
Provo con k=3 e l'equivalenza è soddisfatta.
$$ 3^{561} \equiv 3 \mod 561 $$
Provo con k=4 e l'equivalenza è soddisfatta.
$$ 4^{561} \equiv 4 \mod 561 $$
Questo dimostra che il piccolo teorema di Fermat, da solo, non è sufficiente per distinguere i numeri primi dai composti, specialmente per i numeri di Carmichael.
Nota. Per evitare di essere ingannati da pseudoprimi di Fermat, si usano test più robusti, come il Test di Miller-Rabin oppure test deterministici come il test di Lucas-Lehmer per i numeri di Mersenne o il test di AKS (Agrawal-Kayal-Saxena).
Test di Miller-Rabin
Il test di Miller-Rabin è un algoritmo probabilistico per determinare se un numero \( n > 3 \) è primo.
Può identificare un numero come composto con certezza oppure come "probabilmente primo" con un margine di errore pari a $ \frac{1}{4^k} $ dove $ k $ sono le basi utilizzate per verificare il risultato.
Il test consiste nelle seguenti fasi:
- Decomposizione
Scrivo il numeroi \( n-1 \) come \( 2^s \cdot d \), dove \( d \) è dispari. Questo si ottiene dividendo \( n-1 \) per 2 fino a ottenere un valore dispari. - Scelta di una base \( a \)
Scelgo una base \( a \) casualmente nell'intervallo \( 2 \leq a \leq n-2 \). - Calcolo iniziale
Calcolo \( x = a^d \mod n \). Se \( x \equiv 1 \pmod{n} \) o \( x \equiv n-1 \pmod{n} \), il test per la base \( a \) è superato. Il numero è probabilmente primo. In caso contrario, procedo con le iterazioni successive. - Iterazioni successive
Calcolo \( x = x^2 \mod n \) fino a \( s-1 \) volte:
- Se \( x \equiv n-1 \pmod{n} \) in una qualsiasi iterazione, il test è superato per \( a \). Il numero è probabilmente primo.
- Se \( x \equiv 1 \pmod{n} \) in un'iterazione intermedia, \( n \) è composto.
Poiché il test può generare dei falsi positivi, è consigliabile ripeterlo con diverse basi \( a \). Se \( n \) supera il test per tutte le basi, è considerato probabilmente primo con una probabilità di errore molto bassa.
Esempio
Verifico se n=7 p un numero primo.
$$ n = 7 $$
Scrivo il numero $ n -1 = 6 $ nella forma $ 2^s \cdot d $ dove $ d $ è un numero dispari.
$$ n - 1 = 6 = 2^1 \cdot 3 $$
Quindi $ s=1 $ e $ d= 3 $.
Eseguo la fase iniziale del test di primalità con una base scelta tra $ 2 \leq a \leq n-2 = 5 $
$$ x = a^d \mod n $$
$$ x = 2^3 \mod 7 $$
$$ x = 8 \mod 7 $$
Il risultato è $ x=1 $ perché $ 8:7 = 1 $ con resto $ r = 1 $.
$$ x =1 $$
Poiché $ x \equiv 1 \pmod{7} $ il numero $ n = 7 $ è probabilmente primo secondo il test di Miller-Rabin. Non c'è bisogno di svolgere iterazioni successive.
Teorema di Wilson
Un numero n è un numero primo se e solo se $$ (n-1)! \equiv -1 \mod n $$
Questo metodo ha però uno svantaggio, qualsiasi funzione fattoriale cresce più che esponenzialmente.
E' quindi difficoltoso da applicare per numeri molto grandi.
Esempio
Verifico se n=7 è un numero primo
$$ (n-1)! \equiv -1 \mod n $$
$$ (7-1)! \equiv -1 \mod 7 $$
$$ 6! \equiv -1 \mod 7 $$
$$ 6·5·4·3·2·1 \equiv -1 \mod 7 $$
$$ 720 \equiv -1 \mod 7 $$
$$ 6 \equiv -1 \mod 7 $$
Il numero 6 è congruente con -1 modulo 7.
Pertanto n=7 è un numero primo.
Nota. Dire $$ 6 \equiv -1 \mod 7 $$ equivale a $$ 6 + 1 \equiv 0 \mod 7 $$
E così via.
