Pseudoprimi di Eulero
Un numero composto e dispari \( n \) è detto pseudoprimo di Eulero rispetto a un intero coprimo \( 1<a<n \) se soddisfa la seguente proprietà: \[ b^{(n-1)/2} \equiv \left( \frac{b}{n} \right) \pmod{n} \]
Questo criterio posso utilizzarlo per verificare se un numero dispari \( n \) è primo usando una proprietà particolare.
Il numero \( n \) non è un numero primo se trovo un numero coprimo \( a \) ossia tale che $ MCD(n,a)=1 $ per cui questa relazione non è vera:
\[ \left( \frac{a}{n} \right) = a^{(n-1)/2} \pmod{n} \]
Dove \(\left( \frac{a}{n} \right)\) è il simbolo di Legendre, che calcola una sorta di "relazione speciale" tra \( a \) e \( n \).
Nota. Il simbolo di Legendre assume il valore \(1\) se \( a \) è un residuo quadratico modulo \( p \), ossia se esiste un intero \( x \) tale che $$ x^2 \equiv a \pmod{p} $$ Se \( a \) non è un residuo quadratico modulo \( p \), allora il simbolo di Legendre è \(-1\). Infine, se \( p \) divide \( a \), il simbolo di Legendre assume il valore \(0\). Il simbolo di Legendre si applica solo quando \( p \) è un numero primo. Tuttavia, esiste una generalizzazione anche per i numeri composti, nota come simbolo di Jacobi.
Un esempio pratico
Considero il numero composto e dispari \( n = 15 \).
Prendo un numero intero $ 1<a<15 $ che sia relativamente primo con \( n \).
Ad esempio, il numero 2.
$$ a=2 $$
Si tratta di un numero coprimo con 15 perché non hanno divisori in comune.
$$ MCD(2,15)=1 $$
A questo punto verifico se è un numero pseudoprimo di Eulero, ossia se soddisfa la condizione.
\[ \left( \frac{a}{n} \right) = a^{(n-1)/2} \pmod{n} \]
In questo caso $ a=2 $ e $ n =15 $
\[ \left( \frac{2}{15} \right) = 2^{(15-1)/2} \pmod{15} \]
\[ \left( \frac{2}{15} \right) = 2^{(14)/2} \pmod{15} \]
\[ \left( \frac{2}{15} \right) = 2^{7} \pmod{15} \]
\[ \left( \frac{2}{15} \right) = 128 \pmod{15} \]
Facendo i calcoli la congruenza è \( 128 \mod 15 = 8 \)
\[ \left( \frac{2}{15} \right) = 128 \equiv 8 \pmod{15} \]
In questo caso il simbolo di Legendre diventa \(\left( \frac{2}{15} \right) = 1\)
Nota. Il risultato \(\left(\frac{2}{15}\right) = 1\) indica che \(2\) è un "residuo quadratico" rispetto al prodotto \(15 = 3 \cdot 5\), secondo la generalizzazione data dal simbolo di Jacobi che si applica quando il modulo $ n $ è un numero composto.
Poiché \( 8 \neq 1 \), posso concludere che \( 15 \) non è primo.
Questo significa che \( n \), pur non essendo primo, "si comporta" in un certo senso come un numero primo rispetto alla base \( a \).
La relazione tra gli pseudoprimi di Eulero e quelli di Fermat
Se un numero \(n\) è uno pseudoprimo di Eulero in base \(b\), allora è anche uno pseudoprimo (di Fermat) in base \(b\).
Gli pseudoprimi di Eulero sono un sottoinsieme più ristretto rispetto agli pseudoprimi di Fermat.
In altre parole, ogni pseudoprimo di Eulero è anche un pseudoprimo di Fermat ma non vale l'inverso. Non tutti gli pseudoprimi di Fermat sono pseudoprimi di Eulero.
Nota. Questo significa che gli pseudoprimi di Eulero selezionano meno elementi rispetto a quelli di Fermat, perché richiedono di soddisfare una condizione più forte, che coinvolge anche proprietà quadratiche (attraverso il simbolo di Legendre).
La definizione di pseudoprimo di Eulero implica che:
$$ b^{(n-1)/2} \equiv \left(\frac{b}{n}\right) \pmod{n} $$
Dove \(\left(\frac{b}{n}\right)\) è il simbolo di Legendre.
Elevando entrambi i membri della relazione al quadrato, ottengo:
\[ \left(b^{(n-1)/2}\right)^2 \equiv \left(\left(\frac{b}{n}\right)\right)^2 \pmod{n}. \]
\[ b^{2 \cdot (n-1)/2} \equiv \left(\frac{b}{n}\right)^2 \pmod{n} \]
\[ b^{n-1} \equiv \left(\frac{b}{n}\right)^2 \pmod{n} \]
Il simbolo di Legendre $ \left(\frac{b}{n}\right) $ può valere solo \( \pm1 \), quindi elevandolo al quadrato \(\left(\frac{b}{n}\right)^2 \) è sempre \(1\) modulo \(n\).
\[ b^{n-1} \equiv 1 \pmod{n} \]
Quest'ultima è la definizione di pseudoprimo di Fermat in base \(b\).
Quindi, ogni pseudoprimo di Eulero è automaticamente anche uno pseudoprimo di Fermat.
Ma non vale il viceversa. Non tutti gli pseudoprimi di Fermat sono anche pseudoprimi di Eulero.
Esempio
Il numero composto \(n = 91\) è uno pseudoprimo di Fermat in base \(a=3\) perché soddisfa il teorema di Fermat:
$$ a^{p-1} \equiv 1 \pmod{p} $$
$$ 3^{90} \equiv 1 \pmod{91} $$
Ma non è uno pseudoprimo di Eulero in base \(a=3\), perché non soddisfa la relazione più forte:
\[ a^{(n-1)/2} \equiv \left( \frac{a}{n} \right) \pmod{n} \]
\[ 3^{45} \equiv \left(\frac{3}{91}\right) \pmod{91} \]
Nota. Viceversa, il numero composto \(n = 341 \) è uno pseudoprimo di Eulero in base \(a=2\) ed è anche uno pseudoprimo di Fermat nella stessa base.
Note
Alcune note e osservazioni aggiuntive sui numeri pseudoprimi di Eulero.
- Gli pseudoprimi di Eulero hanno meno falsi positivi rispetto agli pseudoprimi di Fermat
Sia \( n \) un intero composto, positivo e dispari. Il numero delle basi \( b < n \), coprime con \( n \), per cui \( n \) risulta uno pseudoprimo di Eulero, è al massimo la metà di tutte le basi \( b \) tali che \( \text{MCD}(b, n) = 1 \).
Questo significa che gli pseudoprimi di Eulero sono più affidabili degli pseudoprimi di Fermat nei test di primalità, perché si basano su una condizione più restrittiva. Negli pseudoprimi di Fermat, invece, il numero dei falsi positivi è "almeno la metà" di tutte le basi coprime. In certi casi addirittura tutte le basi sono falsi positivi, come accade ad esempio nei numeri di Carmichael. Quindi, i falsi positivi negli pseudoprimi di Fermat sono molti di più. - Proprietà moltiplicativa delle basi negli pseudoprimi di Eulero
Se un numero dispari non primo è pseudoprimo di Eulero per due basi \( b_1 \) e \( b_2 \), allora sarà pseudoprimo anche per il prodotto delle due basi \( b_1 b_2 \) e per il prodotto di \( b_1 \) con l'inverso di \( b_2 \) modulo \( n \). - Esistenza di un non-residuo quadratico
Dato un numero dispari \( n > 1 \) che non sia un quadrato perfetto, esiste sempre un intero positivo \( b < n \), primo con \( n \), tale che la base \( b \) è un non-residuo quadratico modulo \( n \), ovvero il simbolo di Legendre è \( \left( \frac{b}{n} \right) = -1 \). - Esistenza di almeno una base in cui il numero n non è pseudoprimo
Per ogni numero composto dispari \( n \), esiste almeno un numero intero \( b < n \), coprimo con \( n \), per cui \( n \) non è pseudoprimo di Eulero.
E così via.
