Obliczanie modulo

disrupter · Post autor: **disrupter** » 12 wrz 2010, o 21:13

Mam problem z obliczeniem:
\(\displaystyle{ 2 ^{3941} mod3943}\).
Nie wiem co trzeba zrobic w tak duzym modulo natomiast wiem jak obliczyc np:
\(\displaystyle{ 2 ^{3948} mod3943}\)
gdy potega przy liczbie jest wieksza niz liczba modulo.
Wiem,że można to rozpisać na:
\(\displaystyle{ 2^{3943}*2 ^{-2}mod3943}\) ale nie wiem co potem. Prosze o pomoc

Fingon · Post autor: **Fingon** » 12 wrz 2010, o 21:15

Wskazówka: Małe twierdzenie Fermata.

disrupter · Post autor: **disrupter** » 12 wrz 2010, o 21:16

to akurat wiem.
Wtedy zostaje:
\(\displaystyle{ 2 ^{-2}mod3943}\) i nie wiem co z tym dalej zrobic

Fingon · Post autor: **Fingon** » 12 wrz 2010, o 21:18

Ile wynosi \(\displaystyle{ 2^{-1}\ mod 3943}\)?
Wskazówka: rozszerzony algorytm Euklidesa

disrupter · Post autor: **disrupter** » 12 wrz 2010, o 21:23

Próbowałem ale nie wiem o co chodzi. Mógłbyś to rozpisać?? byłbym wdzieczny