Proprietà moltiplicativa delle basi negli pseudoprimi di Eulero

Se \( n > 1 \) è un numero dispari non primo ed è uno pseudoprimo di Eulero nelle basi \( b_1 \) e \( b_2 \), ossia con due numeri composti \( \text{MCD}(b_1, n) = \text{MCD}(b_2, n) = 1 \) nell'intervallo $ 1 < b \ n $, allora \( n \) è pseudoprimo anche per il prodotto delle due basi \( b_1 b_2 \) e per il prodotto \( b_1 b_2^{-1} \), dove \( b_2^{-1} \) è l'inverso di \( b_2 \) modulo \( n \).

In altre parole, la pseudoprimalità di Eulero si conserva quando si moltiplicano le basi o si usa l'inverso modulare di una di queste.

Questo riflette una struttura interna chiusa degli pseudoprimi di Eulero che li rende "stabili" rispetto a certe operazioni sulle basi.

A cosa serve? Questa proprietà mi permette di trovare altri pseudoprimi di Eulero a partire da due basi già note nell'intervallo $ 1<b<n $. Quindi, se già conosco due basi che generano uno pseudoprimo di Eulero, posso usarle per trovare anche le eventuali altre basi. Ad esempio, se sto facendo un test di primalità, evito di dover provare ogni base singolarmente. Basta trovarne un paio e usare la moltiplicazione per generarne altre senza sforzo.

Un esempio pratico

Considero il modulo dispari \( n = 21 \) e le basi \( b_1 = 8 \) e \( b_2 = 13 \).

I numeri 8 e 13 sono coprimi con 21.

$$ \text{MCD}(8, 21) = 1 $$

$$ \text{MCD}(13, 21) = 1 $$

Quindi le basi sono valide.

1] Verifica della pseudoprimalità delle basi

Verifico la pseudoprimalità di \( n = 21 \) nelle basi \( b_1 = 8 \) e \( b_2 = 13 \)

Un numero \( n \) è pseudoprimo di Eulero nella base \( b \) se:

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

Per \( b_1 = 8 \):

\[ 8^{(21-1)/2}  \pmod{21} \]

\[ 8^{(20)/2}  \pmod{21} \]

\[ 8^{10}  \pmod{21} \]

Sapedo che \( 8^2 = 64 \equiv 1 \pmod{21} \) deduco che:

$$ 8^{10} = (8^2)^5 \equiv 1^5 = 1 \pmod{21} $$

Quindi, \( n = 21 \) è pseudoprimo nella base \( b_1 = 8 \).

Per \( b_2 = 13 \)

\[ 13^{(21-1)/2} \pmod{21} \]

\[ 13^{(20)/2} \pmod{21} \]

\[ 13^{10} \pmod{21} \]

Sapendo che \( 13^2 = 169 \equiv 1 \pmod{21} \)

$$ 13^{10} = (13^2)^5 \equiv 1^5 = 1 \pmod{21} $$

Quindi, \( n = 21 \) è pseudoprimo anche nella base \( b_2 = 13 \).

2] Verifica della pseudoprimalità dei prodotti delle basi

A questo punto devo verificare se \( n=21 \) è pseudoprimo anche nelle basi \( b_1 b_2 \) e \( b_1 b_2^{-1} \)

Calcolo il prodotto delle basi:

\[ b_1 b_2 = 8 \cdot 13 = 104 \]

Sapendo che \( 104 \equiv 20 \mod 21 \):

\[ 20^{10} \pmod{21} \]

Verifico se \( n = 21 \) è pseudoprimo nella base \( 20 \):

\[ 20^{(21-1)/2}  \pmod{21} \]

\[ 20^{(20)/2} \pmod{21} \]

\[ 20^{10} \pmod{21} \]

Poiché \( 20^2 = 400 \equiv 1 \pmod{21} \)

\[ 20^{10} = (20^2)^5 \equiv 1^5 = 1 \pmod{21} \]

Quindi, \( n = 21 \) è un pseudoprimo di Eulero nella base \( b_1 b_2 = 20 \).

Infine, verifico se \( 21 \) è uno pseudoprimo anche il prodotto della prima base per l'inverso della seconda base \( b_1 b_2^{-1} \):

\[ b_1 b_2^{-1}  \pmod{21} \]

\[ 8 \cdot  b_2^{-1}  \pmod{21} \]

Calcolo l'inverso di \( b_2 = 13 \) modulo \( n = 21 \) ovvero cerco un intero \( b_2^{-1} \) tale che \(  13 \cdot b_2^{-1} \equiv 1 \pmod{21} \)  Utilizzo l'algoritmo euclideo esteso e dopo i calcoli, ottengo \( b_2^{-1} = 13 \pmod{21} \)

\[ 8 \cdot  13  \pmod{21} \]

\[ 104 \equiv 20  \pmod{21} \]

\[ 20  \pmod{21} \]

Poiché in questo caso l'inverso della seconda base coincide con la seconda base stessa \( b_2 =  b_2^{-1} = 13 \) anche il prodotto è lo stesso del caso precedente \( b_1 b_2 = b_1 b_2^{-1} = 8 \cdot 13 = 104 \)

Quindi, so già che \( n = 21 \) è pseudoprimo nella base \( b_1 b_2^{-21} = 20 \), non occorre rifare i calcoli.

\[ 20 \equiv 1  \pmod{21} \]

La proposizione è verificata.

E così via.