Esercizio - Test di Miller-Rabin su 221 e 561 e confronto con il test di Fermat

Testo. Il test di Miller-Rabin scrive $n-1=2^sd$ con $d$ dispari e dichiara $a$ testimone di composizione se $a^d\not\equiv1$ e $a^{2^rd}\not\equiv-1\pmod n$ per $r=0,\dots,s-1$ .

Per $n=221$ eseguire il test con $a=2$ e con $a=174$ .
Per $n=561=3\cdot11\cdot17$ calcolare $2^{560}\bmod561$ (test di Fermat) e poi eseguire Miller-Rabin con $a=2$ e $a=50$ .
Quante basi $a\in[1,n-1]$ sono bugiarde per $221$ e per $561$ (contare con un programma)? Qual è l'errore dopo $k=10$ basi indipendenti e quale quello garantito dal teorema di Rabin ( $\ge3/4$ di testimoni)?

Teoria: Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione (sezione su Miller-Rabin).

Soluzione

Punto 1, $n=221=13\cdot17$ . $n-1=220=4\cdot55$ , quindi $s=2$ , $d=55$ . Si calcolano $a^{55}$ e $a^{110}$ modulo $221$ .

$a=2$ : $2^{55}\equiv128$ , $2^{110}\equiv128^2=16384=74\cdot221+30\equiv30$ . I valori $128$ e $30$ non sono $1$ né $220=-1$ : $2$ è un testimone, quindi $221$ è composto (certo).
$a=174$ : $174^{55}\equiv47$ e $174^{110}\equiv47^2=2209=9\cdot221+220\equiv-1$ . La condizione $a^{2d}\equiv-1$ è soddisfatta: $174$ è un bugiardo (non prova nulla, benché $221$ sia composto).

Punto 2, $n=561$ . $n-1=560=16\cdot35$ , $s=4$ , $d=35$ .

Fermat: $2^{560}\equiv1\pmod{561}$ . Il test di Fermat $a^{n-1}\equiv1$ passa (561 è un numero di Carmichael, lo passa per ogni base coprima, $320$ basi): non lo smaschera.
Miller-Rabin con $a=2$ : i valori $2^{35\cdot2^r}$ per $r=0,1,2,3$ sono $263,\ 166,\ 67,\ 1$ . Nessuno degli $r=0,\dots,3$ vale $-1=560$ e $x_0=263\ne1$ : $2$ è un testimone. Il valore $67$ è una radice quadrata di $1$ diversa da $\pm1$ ( $67^2=4489=8\cdot561+1$ ): in un campo non esisterebbe, quindi $561$ non è primo.
Con $a=50$ : $50^{35}\equiv560=-1$ , già al primo passo: bugiardo.

Punto 3. Un programma che prova tutte le basi $1,\dots,n-1$ trova:

$n=221$ : bugiardi $\{1,21,47,174,200,220\}$ , cioè $6$ su $220$ ; testimoni $214$ , il $97{,}3\%$ .
$n=561$ : bugiardi $\{1,50,101,103,256,305,458,460,511,560\}$ , $10$ su $560$ ; testimoni il $98{,}2\%$ . Il test di Fermat ha $320$ basi che passano.

Con $k=10$ basi indipendenti uniformi la probabilità di errore (tutte bugiarde) è, per i valori veri, $(6/220)^{10}\approx2\cdot10^{-16}$ per $221$ e $(10/560)^{10}\approx3\cdot10^{-18}$ per $561$ ; il teorema di Rabin garantisce per ogni composto $\le(1/4)^{10}=9{,}5\cdot10^{-7}$ , molto più largo.

Risultati: $221$ : $2$ testimone, $174$ bugiardo, $6/220$ bugiardi. $561$ : Fermat passa, Miller-Rabin con $a=2$ lo smaschera, $10/560$ bugiardi.

python

def valori(a, n):
    d, s = n - 1, 0
    while d % 2 == 0: d //= 2; s += 1
    return [pow(a, d * 2**r, n) for r in range(s)]

def bugiardo(a, n):
    v = valori(a, n)
    return v[0] == 1 or (n - 1) in v

print(valori(2, 221), valori(174, 221), pow(2, 560, 561), valori(2, 561), valori(50, 561))
for n in (221, 561):
    L = [a for a in range(1, n) if bugiardo(a, n)]
    print(n, len(L), L, sum(pow(a, n - 1, n) == 1 for a in range(1, n)))
print((6 / 220)**10, (10 / 560)**10, 0.25**10)

Versione ripasso

Test: $n-1=2^sd$ ; $a$ testimone se $a^d\not\equiv1$ e $a^{2^rd}\not\equiv-1$ per $r<s$ (Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione).
$n=221$ ( $s=2$ , $d=55$ ): $a=2$ : $128,30$ , testimone; $a=174$ : $47,220=-1$ , bugiardo. Bugiardi $\{1,21,47,174,200,220\}$ : $6/220$ .
$n=561$ ( $s=4$ , $d=35$ ): Fermat $2^{560}\equiv1$ passa (Carmichael, $320$ basi passano). Miller-Rabin $a=2$ : $263,166,67,1$ , testimone ( $67^2\equiv1$ radice non banale). $a=50$ : $-1$ , bugiardo. Bugiardi $10/560$ .
Errore dopo $k=10$ basi: valori veri $\approx2\cdot10^{-16}$ e $3\cdot10^{-18}$ ; garanzia di Rabin $4^{-10}=9{,}5\cdot10^{-7}$ .
Errori tipici: fermarsi al solo controllo $a^{n-1}\equiv1$ ; dimenticare il passo $r=0$ (basta $a^d\equiv\pm1$ ); non vedere che una radice di $1$ diversa da $\pm1$ prova che $n$ è composto.

Esercizi su questo argomento

Esercizio - Moneta a due teste e regola di Bayes per le risposte di un test randomizzato (lezioni MIT)

Teoria collegata

Algoritmi randomizzati - Monte Carlo, Las Vegas e amplificazione