Test di Miller-Rabin

[Danyzzz]

ciao a tutti!
Chi potrebbe spiegarmi come applicare il metodo di risoluzione del test di miller rabin???
Ecco un esempio di esercizio.

Applicare a n = 91 il test di Miller-Rabin con base a = 3.
Grazie!

[Riemann42]

Il test di Miller Rabin è un test deterministico di primalità, ovvero serve per determinare se un dato numero n è primo o no.
Noi abbiamo:
$n=91$
$n-1=90$
Ora scriviamo $n-1$ come prodotto di $2^{s}*d$, con $s$ un intero e $d$ un numero dispari, ovvero vediamo per quante volte 90 è divisibile per 2: ovviamente una sola volta ( $90:2=45$)
$n-1=90=2^{1}*45$

Quindi se troviamo un $a$ tale che

$a^{d} != 1 mod n$ e $a^{2^rd} != -1 mod n$ per ogni $0<=r<=s-1$

allora n è composto.
Attenzione! Se le due equazioni qui sopra fossero entrambe vere ($-=$ al posto di $!=$) non è detto che n sia primo, semplicemente si cerca un altro a che funzioni. Se non funziona per ogni $a
Tu hai come base $a=3$, abbiamo trovato $d=45$, quindi:

$3^45 mod 91 -= 36 != 1$
$3^{2^{0}*45} mod 91 -= 36 != -1$
$3^{2^{1}*45} mod 91 -= 51 != -1$

Quindi 91 è composto (infatti 91=7*13).

Se hai altre domande avvisa!