Pseudoprimi forti

Uno pseudoprimo forte è un numero composto dispari \( n \), cioé non primo, che passa il test di Miller-Rabin per una certa base \( b \) senza essere effettivamente primo.

Questo significa che esiste un numero che, in modo fortuito, soddisfa le condizioni del test di primalità anche se non dovrebbe. In altre parole, sembra un numero primo ma non lo è.

Ma c’è un problema per chi vuole usarli per barare: sono rari e non funzionano sempre.

Come riconoscere un numero pseudoprimo forte

Si parte da un numero dispari \( n \) e lo si scrive nella forma:

\[ n = 2^s t + 1 \]

Dove \( t \) è dispari e \( s \) è il numero massimo di volte che posso dividere \( n - 1 \) per 2 prima di ottenere un numero dispari.

Nota. Questa forma può essere calcolata in modo più semplice usando l'equazione equivalente \[ n-1 = 2^s \cdot t  \]

Il numero \( n \) è uno pseudoprimo forte in base \( b \) se verifica almeno una delle seguenti condizioni:

• La prima condizione
  La base \( b^t \), che è una delle prime potenze di \( b \) mod \( n \), restituisce già 1. Questo è tipico dei numeri primi. \[ b^t \equiv 1 \mod n \]
• La seconda condizione
  Esiste un esponente \( r \) nell'intervallo \( 0 \leq r < s \) tale che una delle potenze di \( b \) restituisce -1 modulo \( n \), un'altra proprietà che accade per i numeri primi.  \[ b^{2^r t} \equiv -1 \mod n  \]

Se \( n \) soddisfa almeno una di queste condizioni, allora si comporta come un numero primo nei test di Miller-Rabin, anche se in realtà è composto, ed è detto pseudoprimo forte.

Nota. Un numero composto, in genere, fallisce entrambe le condizioni del test di Miller-Rabin per molte basi, ed è proprio questa caratteristica che lo rende efficace nel distinguere i numeri primi dai composti. Sebbene esistano numeri composti particolari, come gli pseudoprimi forti, che possono ingannare il test per alcune basi, questi casi sono rari. La maggior parte dei numeri composti ha poche basi che li ingannano. Il test di Miller-Rabin rimane estremamente affidabile se applicato con più basi diverse. Infatti, ripetendo il test su un numero sufficiente di basi, il rischio di falsi positivi, ossia numeri composti che vengono erroneamente identificati come primi, diventa trascurabile.

Un esempio pratico

Il numero \( n = 25 \) è pseudoprimo forte in base \( b = 7 \)

Scrivo \( n-1 = 25 - 1 = 24 \) nella forma:

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

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

Verifico se soddisfa almeno una tra le condizioni di pseudoprimalità forte.

1] La prima condizione

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

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

Poiché $ 7 \ne 18 $ la prima condizione non è soddisfatta.

2] La seconda condizione

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

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

Provo alcuni valori di $ r $ a nell'intervallo $ 0 \le r \le s=3 $ per vedere se esiste almeno una congruenza uguale a -1.

$$ 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 è soddisfatta perché $ 24 \equiv -1 \mod 25 $, ossia  \( 7^6 \) è congruo a \(-1\) nel modulo $ n=25 $.

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

Esempio 2

Considero il numero \( n = 2047 \) e verifico se è pseudoprimo forte in base \( b = 2 \).

Scrivo \( n-1 = 2047 - 1 = 2046 \) nella forma:

\[ 2046 = 2^s \cdot t = 2^1 \cdot 1023 \]

Il numero 2046 posso dividerlo una sola volta per 2, quindi $ s=1$ e $ t = 1023 $ perché $ 2046 = 2 \cdot 1023 $

Verifico se soddisfa almeno una delle condizioni degli pseudoprimi forti.

1] La prima condizione

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

$$ 2^{1023} = 1 \equiv 1 \mod 2047 $$

La prima condizione è soddisfatta, quindi \( 2047 \) è uno pseudoprimo forte perché si comporta come un primo nel test di Miller-Rabin per la base \( b = 2 \) anche se è composto \( 2047 = 23 \cdot 89 \).

In questo caso non occorre verificare la seconda condizione, perché posso già affermare che il numero composto \( n= 2047 \) è uno pseudoprimo forte nella base \( b=2 \).

In conclusione, gli pseudoprimi forti sono numeri composti che "ingannano" alcuni test di primalità basati sull'esponenziazione modulare. 

Note aggiuntive

Alcune note e osservazioni a margine sugli pseudoprimi forti

• Gli pseudoprimi forti di un numero sono al massimo 1/4 delle basi coprime del numero
  Per un numero dispari e composto \( n \), il numero di basi \( b \) per cui \( n \) risulta essere uno pseudoprimo forte è al massimo un quarto di tutte le basi coprime con \( n \) (cioè, che soddisfano \( \gcd(b, n) = 1 \)). In altre parole, se considero tutte le possibili basi \( b \) minori di \( n \) che non condividono fattori con \( n \), al massimo il 25% di queste basi può far sembrare \( n \) uno pseudoprimo forte. Questa proprietà è utile perché mi dice che il test degli pseudoprimi forti (come il test di Miller-Rabin) ha una probabilità di errore al più 1/4 per ogni base scelta casualmente. Quindi, testando più basi, si riduce drasticamente la possibilità di classificare erroneamente un numero composto come primo.

  Esempio. Nell'esempio precedente ho verificato tutte le basi di \( n=25 \). Il numero 25 ha 19 basi ossia interi coprimi tra 1 e 24 ma solo per tre basi ( 7, 18, 24 ) il numero 25 è uno pseudoprimo forte. Quindi, in questo caso le basi in cui è pseudoprimo forte sono il 15.8%, meno del 25%.

• Relazione tra pseudoprimi forti e pseudoprimi in base \( b \) di Fermat
  Tutti gli pseudoprimi forti in base \( b \) sono anche pseudoprimi di Fermat in base \( b \). Questo accade perché il test di pseudoprimalità forte è un raffinamento del test di Fermat. Ad esempio, un numero \( n \) è uno pseudoprimo di Fermat in base \( b \) se  \[ b^{n-1} \equiv 1 \pmod{n} \] E' uno pseudoprimo forte e in base \( b \) se esiste un \( s \) tale che \( n - 1 = 2^s d \) con \( d \) dispari e  \[ b^d \equiv \pm 1 \pmod{n} \quad \text{oppure} \quad b^{2^r d} \equiv -1 \pmod{n} \text{ per qualche } 0 \leq r < s \] Quindi, ogni numero che supera il test forte supera anche quello di Fermat. Tuttavia, il contrario non è vero: ci sono pseudoprimi di Fermat che non sono pseudoprimi forti.
• Relazione tra pseudoprimi forti e pseudoprimi di Eulero
  Ci sono due importanti relazioni tra gli pseudoprimi forti e quelli di Eulero.
  1] se \( n \) è uno pseudoprimo forte in base \( b \), allora è anche uno pseudoprimo di Eulero in base \( b \).
  2] se \( n \equiv 3 \pmod{4} \), allora un numero \( n \) è pseudoprimo forte in base \( b \) se e solo se è anche pseudoprimo di Eulero in base \( b \). In questo caso particolare (e solo in questo caso) i due concetti sono equivalenti. Viceversa, se \( n \not \equiv 3 \pmod{4} \) non c'è alcuna relazione, quindi esistono anche numeri che soddisfano una condizione ma non l'altra.
  

  A cosa serve saperlo? Questa relazione semplifica i test di primalità, poiché per verificare se un numero è uno pseudoprimo forte posso usare il test di Eulero, che è meno computazionalmente costoso del test di pseudoprimalità forte. Questo riduce i calcoli nei test di Miller-Rabin e nei sistemi crittografici.

E così via.