Test di primalita' Miller-Rabin

[sassanduri]

Buongiorno,
qualcuno potrebbe spiegarmi bene questo test di primalita' con magari degli esercizi svolti? (la cosa piu' importante in realta' sono gli esercizi, perche' sugli appunti della mia prof non ci sono ).
Inoltre se siete molto gentili , potete spiegarmi perche' 341 non e' primo? sul libro dice che e' pseudoprimo con 2 perche' $ 2^340(mod341)=1 $, e fin qui ci sono. Non capisco perche' $ 3^340(mod341)=56 $ e non 1, venendo $ mcd(3,341)=1 $ .

Grazie mille in aticipo e buonagiornata a tutti

[Gi8]

Se $a$ ed $n$ sono coprimi, non è sempre vero che $a^(n-1) -=1 (mod n)$.
E' vero solo se $n$ è primo.

Il risultato giusto è questo: $a^(varphi(n))-=1 (mod n)$

[sassanduri]

ok perfetto allora per calcolare $ 3^340 (mod341) $, sapendo che $ 341 = 11 * 31 $ e quindi $ \varphi (341) = 300 $, ho svolto cosi:

$ 3^340 (mod341) = 3 ^300 * 3^40 (mod341) = 1 * 3^40 (mod341) $

sapendo che $ 3^6 = 729 = 47 (mod 341) $ e che $ 40 = 6*6 + 4 $

$ = 47 * 47 * 47 * 47 * 47 * 47 * 3^4 (mod 341) $

poi $ 47 * 47 = 163 (mod341) $

quindi

$ 163 * 163 * 163 * 3^4 (mod 341) == 4330747 * 3^4 (mod341) $

$4330747 = 47 (mod341)$ quindi $ 47 * 3^4 (mod 341) = 3807 (mod341) = 56 (mod341) $

Allora, il risulato e' giusto, ma sono sicuro che c'e' un modo piu' semplice di risolverlo, dato che all'esame non potremo usare la calcolatrice ...
Come faccio a risolverla senza fare tutti questi calcoli con numeri improponibili?

Poi qualcuno ha esercizi sui Miller-Rabin?

Ancora grazie mille per l'aiuto.

[Gi8]

Vogliamo risolvere $3^(340) (mod 341)$
Dato che $341=11*31$,
1) risolviamo $3^340 (mod 11)$: $(3^10)^34-=1^34=1 (mod 11)$
2) risolviamo $3^340 (mod 31)$:
$3^10*3^330 -=3^10 =3*27^3=3*(-4)^3= 3*(-64)-=3*(-2) = -6 -= 25(mod 31)$

Ora risolviamo il sistema ${(x-=1 (mod 11)),(x-= 25 (mod 31)):}$
usando ad esempio il teorema cinese del resto. Si ottiene proprio $x-= 56 (mod 341)$

[sassanduri]

Perfetto grazie mille!!! non avevo pensato a separarli ahahah mi sento uno stupido

[sassanduri]

Scusate, avrei anche un altro dubbio: devo vedere se $ 313$ e' primo con il metodo Miller-Rabin in base $2$ e $3$ e non ci riesco. Questo e' quello che ho fatto:
Calcolo $k$ e $m$:
$312 = 2^3 * 39 $
$k=3 , m=39 $

quindi in base $ a=2$

$b0 = a^m (mod n) = 2^39 (mod313) $ .

quello che non capisco e': come faccio a calcolare $2^39 (mod313)$ (che viene $25$) senza fare calcoli assurdi, perche', supponendo che sia primo, non posso scomporre $313$ e fare un sistema piu' semplice.

Grazie mille