Proprietà di non-pseudoprimalità dei numeri composti
Dato un numero composto e dispari \( n > 1 \) e considerando i numeri coprimi con \( n \) nell'intervallo \( 1 < a < n \) $$ \operatorname{MCD}(n, a) = 1 $$ se \( n \) non è pseudoprimo in un dato intero \( a \), allora non sarà pseudoprimo in almeno la metà dei numeri coprimi con \( n \) nello stesso intervallo.
In altre parole, se un numero composto \( n \) fallisce la condizione di pseudoprimalità in una base \( a \) coprima con \( n \), allora fallisce almeno la metà delle altre basi $ b $ coprime con \( n \) tra 1 e \( n \).
Questo limita fortemente l'idea di utilizzare pseudoprimi per testare primalità, ossia per cercare i numeri primi, poiché non è garantito che \( n \) si comporti in modo pseudoprimo nella maggior parte delle basi.
Nota. E questo è il motivo per cui test di primalità più sofisticati, come il Miller-Rabin o il Baillie-PSW, cercano più basi per ridurre i falsi positivi.
Un esempio pratico
Considero \( n = 91 \), che è dispari e non primo, infatti, \( 91 = 7 \cdot 13 \).
I divisori di \( 91 \) sono solo \( 1, 7, 13, 91 \). Quindi, i numeri coprimi con \( 91 \) sono tutti quelli che non sono multipli di \( 7 \) o \( 13 \).
In base alla funzione di Eulero ci sono 72 numeri coprimi con 91 compresi tra 1 e 91
$$ \phi(91) = 91 \cdot \left(1 - \frac{1}{7}\right) \cdot \left(1 - \frac{1}{13}\right) = 91 \cdot \frac{6}{7} \cdot \frac{12}{13} = 72 $$
Quindi ci sono 72 basi \( a \) da verificare con il Teorema di Fermat per capire se sono pseudoprimi o meno con 91.
$$ MCD(n, a)=1 $$
La lista dei numeri coprimi con 91 è la seguente:
1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 27, 29, 30, 31, 32, 33, 34, 36, 37, 38, 40, 41, 43, 44, 45, 46, 47, 48, 50, 51, 53, 54, 55, 57, 58, 59, 60, 61, 62, 64, 66, 67, 68, 69, 71, 72, 73, 74, 75, 76, 79, 80, 81, 82, 83, 85, 86, 87, 88, 89, 90
Verifico una base, ad esempio \( a = 2 \) usando il Piccolo Teorema di Fermat.
$$ a^{n-1} \not\equiv 1 \pmod{n} $$
$$ 2^{90} \not\equiv 1 \pmod{91} $$
Questo significa che \( n = 91 \) non è pseudoprimo in base \( a = 2 \).
Poiché \( n = 91 \) non è pseudoprimo in base \( a = 2 \), allora \( 91 \) non è pseudoprimo in almeno metà delle basi \( 1<a<91 \) coprime con \( 91 \).
Sapendo che ci sono \( \phi(91) = 72 \) basi coprime con \( 91 \), almeno \( 36 \) di queste basi non sono basi in cui \( 91 \) si comporta come pseudoprimo.
| base | Teorema di Fermat | Base in cui 91 è Pseudoprimo |
|---|---|---|
| \( a = 2 \) | \( 2^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 3 \) | \( 3^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 4 \) | \( 4^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 5 \) | \( 5^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 6 \) | \( 6^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 8 \) | \( 8^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 9 \) | \( 9^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 10 \) | \( 10^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 11 \) | \( 11^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 12 \) | \( 12^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 15 \) | \( 15^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 16 \) | \( 16^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 17 \) | \( 17^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 18 \) | \( 18^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 19 \) | \( 19^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 20 \) | \( 20^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 22 \) | \( 22^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 23 \) | \( 23^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 24 \) | \( 24^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 25 \) | \( 25^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 27 \) | \( 27^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 29 \) | \( 29^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 30 \) | \( 30^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 31 \) | \( 31^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 32 \) | \( 32^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 33 \) | \( 33^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 34 \) | \( 34^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 36 \) | \( 36^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 37 \) | \( 37^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 38 \) | \( 38^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 40 \) | \( 40^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 41 \) | \( 41^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 43 \) | \( 43^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 44 \) | \( 44^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 45 \) | \( 45^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 46 \) | \( 46^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 47 \) | \( 47^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 48 \) | \( 48^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 50 \) | \( 50^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 51 \) | \( 51^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 53 \) | \( 53^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 54 \) | \( 54^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 55 \) | \( 55^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 57 \) | \( 57^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 58 \) | \( 58^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 59 \) | \( 59^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 60 \) | \( 60^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 61 \) | \( 61^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 62 \) | \( 62^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 64 \) | \( 64^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 66 \) | \( 66^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 67 \) | \( 67^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 68 \) | \( 68^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 69 \) | \( 69^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 71 \) | \( 71^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 72 \) | \( 72^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 73 \) | \( 73^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 74 \) | \( 74^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 75 \) | \( 75^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 76 \) | \( 76^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 79 \) | \( 79^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 80 \) | \( 80^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 81 \) | \( 81^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 82 \) | \( 82^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 83 \) | \( 83^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 85 \) | \( 85^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 86 \) | \( 86^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 87 \) | \( 87^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 88 \) | \( 88^{90} \equiv 1 \pmod{91} \) | ✅ si |
| \( a = 89 \) | \( 89^{90} \not\equiv 1 \pmod{91} \) | ❌ no |
| \( a = 90 \) | \( 90^{90} \equiv 1 \pmod{91} \) | ✅ si |
Questo esempio mostra che non tutte le basi coprime con \( 91 \) rendono \( 91 \) pseudoprimo.
Anzi, almeno metà delle basi coprime con \( 91 \) non soddisfano la condizione di pseudoprimalità.
La dimostrazione
Considero il gruppo moltiplicativo \( \mathbb{U}(\mathbb{Z}_n) \), che è costituito dall'insieme degli interi \( b \) compresi tra 1 e n−1, che sono coprimi con n.
\[ \mathbb{U}(\mathbb{Z}_n) = \{ b \in \mathbb{Z}_n \mid \operatorname{MCD}(b, n) = 1 \} \]
L'ordine di \( \mathbb{U}(\mathbb{Z}_n) \) è indicato con \( \phi(n) \), dove \( \phi \) è la funzione di Eulero.
Definisco \( P \) è un sottoinsieme di \( \mathbb{U}(\mathbb{Z}_n) \) come l'insieme di tutte le basi \( b \) per cui \( n ) è pseudoprimo.
\[ P = \{ b \in \mathbb{U}(\mathbb{Z}_n) \mid n \text{ è pseudoprimo in base } b \} \]
Questa è la tesi da dimostrare.
Devo dimostrare che se \( n \) non è uno pseudoprimo in base \( a \), allora almeno metà degli elementi di \( \mathbb{U}(\mathbb{Z}_n) \) non appartengono a \( P \).
Nota. Un numero \( n \) è pseudoprimo in base \( b \) se soddisfa: $$ b^{n-1} \equiv 1 \pmod{n} $$ Se \( n \) non è pseudoprimo in base a un particolare \( a \in \mathbb{U}(\mathbb{Z}_n) \), allora: $$ a^{n-1} \not\equiv 1 \pmod{n} $$
Considero un numero \( a \in \mathbb{U}(\mathbb{Z}_n) \) tale che \( a^{n-1} \not\equiv 1 \pmod{n} \), cioè \( a \notin P \) che non appartiene all'insieme P.
Ora definisco un'applicazione che, dato un elemento \( b \in P \), restituisce il prodotto \( ab \mod n \).
$$ f : b \in P \mapsto ab \in \mathbb{U}(\mathbb{Z}_n) $$
Questa mappa è una permutazione di \( \mathbb{U}(\mathbb{Z}_n) \), perché \( a \) è invertibile modulo \( n \).
Se \( b \in P \), allora \( b^{n-1} \equiv 1 \pmod{n} \).
Per verificare se \( ab \in P \), considero:
$$ (ab)^{n-1} = a^{n-1} b^{n-1} $$
Poiché \( b \in P \), so che \( b^{n-1} \equiv 1 \pmod{n} \). Quindi:
$$ (ab)^{n-1} = a^{n-1} \cdot 1 \pmod{n}$$
$$ (ab)^{n-1} = a^{n-1} \pmod{n} $$
Ora, dato che \( a^{n-1} \not\equiv 1 \pmod{n} \), perché per ipotesi \( a \notin P \)), segue che \( ab \notin P \).
Questo implica che la mappa \( f \) manda ogni \( b \in P \) in un elemento \( ab \notin P \).
Poiché l'applicazione \( f \) manda gli elementi di \( P \) fuori da \( P \), segue che il numero di elementi di \( P \) è al massimo la metà degli elementi di \( \mathbb{U}(\mathbb{Z}_n) \):
$$ |P| \leq \frac{\phi(n)}{2} $$
Nota. L'applicazione \( f(b) = ab \) manda ogni elemento di \( P \) fuori da \( P \), quindi non collega nessun elemento di \( P \) con un altro elemento di \( P \). Questo implica che gli elementi fuori da \( P \) devono essere almeno pari a quelli in \( P \), poiché \( f \) sia una permutazione dell'intero gruppo \( \mathbb{U}(\mathbb{Z}_n) \). Pertanto, se il gruppo ha \(\phi(n)\) elementi, segue che l'insieme \(|P| \leq \frac{\phi(n)}{2}\) ne ha la metà.
In conclusione, il complemento di \( P \) in \( \mathbb{U}(\mathbb{Z}_n) \) ha almeno metà degli elementi di \( \mathbb{U}(\mathbb{Z}_n) \).
In altre parole, ci sono almeno \( \phi(n) / 2 \) interi \( b \) tali che \( n \) non è pseudoprimo in base \( b \). E questo dimostra la tesi iniziale.
E così via.
