Relazione tra pseudoprimi forti e pseudoprimi di Eulero

Ci sono due importanti relazioni tra gli pseudoprimi forti e gli pseudoprimi di Eulero:

• Se \( n \) è uno pseudoprimo forte in base \( b \), allora è anche uno pseudoprimo di Eulero in base \( b \).
• Se \( n \) è un numero composto dispari tale che \( n \equiv 3 \pmod{4} \), allora uno pseudoprimo di Eulero in base \( b \) è anche uno pseudoprimo forte in base \( b \).

In altre parole, in alcuni casi particolari i numeri pseudoprimi forti coincidono con gli pseudoprimi di Eulero.

Questo è utile perché il test di Eulero è molto più semplice (e meno costoso) rispetto al test di pseudoprimalità forte, quindi posso ridurre i calcoli per verificare se un numero è uno pseudoprimo forte  nei casi in cui \( n \equiv 3 \pmod{4} \).

Nota. Quando la condizione non viene soddisfatta \( n \not \equiv 3 \pmod{4} \) non c'è alcuna relazione tra i due concetti, quindi esistono anche numeri che soddisfano una condizione ma non l'altra. Tutti gli pseudoprimi forti sono anche pseudoprimi di Eulero ma non è garantito il contrario, poiché il test di pseudoprimalità forte è più selettivo. Quindi, esistono pseudoprimi di Eulero che non soddisfano le condizioni richieste per essere pseudoprimi forti. Soltanto, se \( n \equiv 3 \pmod{4} \) i due concetti coincidono.

Quale è la differenza tra pseudoprimi forti e di Eulero?

Gli pseudoprimi sono numeri composti che si comportano come numeri primi rispetto a certi test di primalità. Due importanti classi di pseudoprimi sono:

• Pseudoprimi forti: soddisfano una certa condizione esponenziale derivata dal test di Miller-Rabin.
• Pseudoprimi di Eulero: soddisfano una condizione più debole, basata sul criterio di Eulero.

La proposizione dice che, per numeri \( n \equiv 3 \pmod{4} \), questi due concetti coincidono.

Un esempio pratico

Il numero \( n = 25 \) è pseudoprimo forte in base \( b = 7 \) perché se scrivo \( n-1 = 25 - 1 = 24 \) nella forma:

\[ 24 = 2^s \cdot t = 2^3 \cdot 3 \]

Ottengo \( s = 3 \) e \( t = 3 \).

Verifico se soddisfa almeno una delle condizioni di pseudoprimalità forte.

1] La prima condizione

$$ b^t \equiv 1 \mod n $$

$$ 7^3 \equiv 18 \mod 25 $$

La prima condizione non è soddisfatta perché $ 7 \ne 18 $.

2] La seconda condizione

$$ b^{2^r t} \equiv -1 \mod n $$

$$ 7^{2^r \cdot 3} \mod 25 $$

Verifico se esiste almeno una congruenza uguale a -1 per almeno un valore di $ r $ a nell'intervallo $ 0 \le r \le s=3 $ .

$$ r = 0 \rightarrow 7^{2^0 \cdot 3} = 7^3 = 7 \not \equiv -1 \mod 25 $$

$$ r = 1 \rightarrow 7^{2^1 \cdot 3} = 7^6 = 24 \equiv -1 \mod 25 $$

Per $ r = 1 $ la condizione di pseudoprimalità forte è soddisfatta

$$ 24 \equiv -1 \mod 25 $$

Quindi, \( 7^6 \) è congruente a \(-1\) nel modulo $ n=25 $.

Sapendo che \( 25 \) è un numero composto \( 25 = 5 \cdot 5 \) ma passa il test di pseudoprimalità forte per la base \( 7 \), deduco che 25 è uno pseudoprimo forte in base 7.

A questo punto verifico se \( n=25 \) è anche uno pseudoprimo di Eulero nella base \( b=7 \)

Per essere uno pseudoprimo di Eulero deve soddisfare questa condizione:

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

\[ 7^{(25-1)/2} = 7^{12} \equiv \left( \frac{7}{25} \right) \pmod{25} \]

Nel lato sinistro $ 7^{12} $ è congruente a 1 nel modulo 25

$$ 7^{12} \equiv 1 \pmod{25} $$

Nel lato destro c'è il simbolo di Jacobi, perché \( n \) è composto, che posso scrivere in questa forma.

$$ \left( \frac{7}{25} \right) = \left( \frac{7}{5} \right) \cdot \left( \frac{7}{5} \right) $$

Ora sia 7 che 5 sono dispari e primi, quindi ottengo il prodotto di due simboli di Legendre.

Applico il criterio di Eulero su $ \left( \frac{7}{5} \right) $

\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p} \]

\[ \left(\frac{7}{5}\right) \equiv 7^{\frac{5-1}{2}} \pmod{5} \]

\[ \left(\frac{7}{5}\right) \equiv 7^2 \pmod{5} \]

\[ \left(\frac{7}{5}\right) \equiv 49 \pmod{5} \]

\[ \left(\frac{7}{5}\right) \equiv 4 \pmod{5} \]

Poiché $ 4 \equiv -1 $ nel modulo 5

\[ \left(\frac{7}{5}\right) \equiv -1 \pmod{5} \]

Pertanto, il simbolo di Jacobi è uguale a 1 ossia al prodotto di -1 per -1.

$$ \left( \frac{7}{25} \right) = \left( \frac{7}{5} \right) \cdot \left( \frac{7}{5} \right) = (-1 ) \cdot (-1) = 1 $$

Quindi, anche il lato destro della condizione precedente è uguale a 1.

\[ 7^{(25-1)/2} = 7^{12} = 1 \equiv \left( \frac{7}{25} \right) \pmod{25} \]

\[ 7^{(25-1)/2} = 7^{12} = 1 \equiv 1  \pmod{25} \]

La condizione di pseudoprimalità di Eulero è soddisfatta, quindi \( n=25 \) è anche uno pseudoprimo di Eulero nella base \( b = 7 \).

Esempio 2

Considero come esempio il modulo \( n = 341 \)

Questo numero è composto \( 341 = 11 \times 31 \), dispari e soddisfa l'equivalenza \( n \equiv 3 \pmod{4} \)

$$ 341 \equiv 3 \pmod{4}  $$

Quindi, in questo caso particolare, se è uno pseudoprimo di Eulero in una base è anche uno pseudoprimo forte nella stessa base.

Scelgo la base \( b = 2 \) perché 2 e 341 sono coprimi \( \gcd(2,341) = 1 \).

Il numero 341 è uno pseudoprimo di Eulero?

Verifico se 341 è pseudoprimo di Eulero in base 2.

\[ 2^{(341-1)/2} \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ 2^{170} \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ (2^{85})^2 \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ (-1)^2 \equiv \left( \frac{2}{341} \right) \pmod{341} \]

\[ 1 \equiv \left( \frac{2}{341} \right) \pmod{341} \]

 Ora calcolo il simbolo di Jacobi \( \left( \frac{2}{341} \right) = 1 \)

\[ 1 \equiv 1 \pmod{341} \]

Poiché \( 2^{170} \equiv 1 \pmod{341} \), la condizione di pseudoprimo di Eulero è verificata.

\[ 2^{170} \equiv 1 \pmod{341} \]

Pertanto, il numero 341 è uno pseudoprimo di Eulero nella base b=2.

Il numero 341 è uno pseudoprimo forte nella stessa base?

Ora verifico se 341 è anche uno pseudoprimo forte in base 2

Scrivo \( 341 - 1 = 340 = 2^2 \cdot 85 \), quindi \( d = 85 \) e \( s = 2 \).

\[ 2^{85} \mod 341 \]

Utilizzando l'aritmetica modulare, trovo che:

\[ 2^{85} \equiv -1 \pmod{341} \]

Poiché ho ottenuto \( -1 \), la condizione di pseudoprimo forte è soddisfatta. Il numero 341 è uno pseudoprimo forte nella base b=2.

In conclusione, il numero \( 341 \) soddisfa entrambe le condizioni: è uno pseudoprimo forte in base \( 2 \) e anche uno pseudoprimo di Eulero in base \( 2 \).

Questo esempio mostra che se \( n \equiv 3 \pmod{4}  \), allora essere pseudoprimo di Eulero equivale a essere pseudoprimo forte in base \( b \).

Dimostrazione

Se è uno pseudoprimo forte allora è anche uno pseudoprimo di Eulero nella stessa base

Poiché \( n \) è uno pseudoprimo forte, può verificarsi una delle seguenti situazioni

A] Caso 1: $ b^t \equiv \pm 1 \pmod{n} $

In questo caso vale la relazione

$$ b^{(n-1)/2} \equiv \pm 1 \pmod{n} $$

Se \( b^t \equiv 1 \pmod{n} \), allora questa relazione si propaga a ogni fattore primo \( p \) di \( n \)

$$  b^t \equiv 1 \pmod{p} $$

Questo implica che l'ordine moltiplicativo di \( b \) modulo \( p \), indicato come \( \operatorname{Gss}(p, b) \), divide \( t \) ed è anche un divisore di \( (p-1)/2 \).

Applicando il criterio di Eulero, si ottiene \( \left( \frac{b}{p} \right) = 1 \), e quindi \( \left( \frac{b}{n} \right) = 1 \), mostrando che \( n \) è uno pseudoprimo di Eulero.

B] Caso 2: Esiste un \( r < s \) tale che \( b^{t \cdot 2^r} \equiv -1 \pmod{n} \)

Considero un divisore primo \( p \) di \( n \) e sfrutto la proprietà \( b^{t \cdot 2^r} \equiv -1 \pmod{p} \).

Questo implica che l'ordine moltiplicativo di \( b \) modulo \( p \) è della forma \( \operatorname{Gss}(p,b) = 2^{r+1} s \), con \( s \) dispari.

Pertanto \( p \equiv 1 \pmod{2^{r+1}} \), ovvero \( p = 2^{r+1} q + 1 \), e quindi la relazione \( \left( \frac{b}{p} \right) = (-1)^q \).

In conclusione, poiché \( s \) è dispari, si ottiene \( \left( \frac{b}{p} \right) = (-1)^q \).

C] Caso generale per \( n \)

Si scrive \( n \) come il prodotto dei suoi fattori primi \( p_i \) con esponenti \( h_i \).

Espando \( n \) modulo \( 2^{r+1} \), si mostra che \( n \equiv 1 \pmod{2^{r+1}} \).

Questo implica che la somma \( \sum_{i=1}^{m} h_i d_i \) è pari, da cui segue che il simbolo di Jacobi \( \left( \frac{b}{n} \right) = 1 \).

Per la definizione di pseudoprimo di Eulero, questo conclude la dimostrazione.

Ho così dimostrato che in entrambi i casi (sia che \( b^t \equiv 1 \) sia che \( b^{t \cdot 2^r} \equiv -1 \)) la condizione per essere uno pseudoprimo forte implica automaticamente la condizione per essere uno pseudoprimo di Eulero.

Se n ≡ 3 mod 4 uno pseudoprimo di Eulero è anche uno pseudoprimo forte

Voglio dimostrare che, se \( n \equiv 3 \pmod{4} \), allora:

\[ n \text{ è pseudoprimo forte in base } b \iff n \text{ è pseudoprimo di Eulero in base } b \]

Divido la dimostrazione in due parti

1] se \( n \) è pseudoprimo di Eulero, allora è anche forte

Se \( n \) è uno pseudoprimo di Eulero in base \( b \), allora è anche pseudoprimo forte in base \( b \).

So che, per definizione di pseudoprimo di Eulero:  

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

Dato che per ipotesi \( n \equiv 3 \pmod{4} \), posso sfruttare la proprietà del simbolo di Jacobi $ \left( \frac{b}{n} \right) $ che può assumere solo valori +1 o -1:

\[ b^{(n-1)/2} \equiv \pm 1 \pmod{n} \]

Ma questa è proprio la condizione che garantisce che \( n \) è pseudoprimo forte in base \( b \), perché, ponendo \( n-1 = 2^1 d \) con \( d = (n-1)/2 \), ottengo che \( b^d \equiv \pm 1 \pmod{n} \).

Quindi la condizione per essere pseudoprimo forte è soddisfatta.

2] Se \( n \) è pseudoprimo forte, allora è anche di Eulero

Per la definizione di pseudoprimo forte, so che:

\[ b^d \equiv \pm 1 \pmod{n} \]

Devo dimostrare che se \( n \) è uno pseudoprimo forte in base \( b \), allora è anche pseudoprimo di Eulero in base \( b \)

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

Poiché per ipotesi \( n \equiv 3 \pmod{4} \), scrivo \( n - 1 = 2^1 d \) con \( d = (n-1)/2 \). 

\[ \left( \frac{b}{n} \right) = \left( \frac{b^d}{n} \right) \]

Sapendo che il simbolo di Jacobi $ \left( \frac{b^d}{n} \right) $ può assumere solo valori \( \pm 1 \).

\[ \left( \frac{b^d}{n} \right) = \pm 1 \]

Ma questo è esattamente ciò che serve per concludere che \( n \) è pseudoprimo di Eulero in base \( b \).

In conclusione, ho dimostrato che le due definizioni coincidono quando \( n \equiv 3 \pmod{4} \).

E così via.