Szybkie potęgowanie modularne.

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
cubasa
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 24 paź 2019, o 12:03
Płeć: Mężczyzna
wiek: 35
Podziękował: 3 razy

Szybkie potęgowanie modularne.

Post autor: cubasa »

Witam. Potrzebuję pomocy w wyjaśnieniu szybkiego obliczania:

1. \(\displaystyle{ 3 ^{17} \bmod 5}\)
2. \(\displaystyle{ 2 ^{26} \bmod 6}\)
3. \(\displaystyle{ 3 ^{217} \bmod 5 }\)

1 przykład udało mi się zrobić, mam nadzieję, że jest oki:

\(\displaystyle{ 3 ^{17} \bmod 5 = \left( \left( 3^{4}\right) ^{4} \cdot 3\right) \bmod 5 = \left( \left( 81\right) ^{4} \cdot 3\right) \bmod 5 = \left( \left( 1\right) ^{4} \cdot 3\right) \bmod 5 = \left( 1 \cdot 3\right) \bmod 5 = 3 \bmod 5 = 3 }\)

Z góry serdecznie dziękuję za pomoc i wyjaśnienie, aby udało mi się to stosować w kolejnych przykładach :roll:
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Szybkie potęgowanie modularne.

Post autor: Premislav »

2. Mamy
\(\displaystyle{ 2^{26}\equiv 0\pmod{2}}\), gdyż jest to liczba parzysta jako potęga dwójki o wykładniku całkowitym dodatnim, a ponadto
\(\displaystyle{ 2^{2}\equiv 1\pmod{3}\\2^{26}=\left(2^{2}\right)^{13}\equiv 1^{13}\pmod{3}}\), zatem
\(\displaystyle{ \begin{cases}2^{26}\equiv 0\pmod{2}\\2^{26}\equiv 1\pmod{3}\end{cases}}\), a stąd łatwo widzimy, że
\(\displaystyle{ 2^{26}\equiv 4\pmod{6}}\).
cubasa
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 24 paź 2019, o 12:03
Płeć: Mężczyzna
wiek: 35
Podziękował: 3 razy

Re: Szybkie potęgowanie modularne.

Post autor: cubasa »

Dzięki za szybką odpowiedź.
Przepraszam, że nie odpisywałem, a dopiero wróciłem.

Znaczy się rozumiem to, co zostało napisane do tego momentu, ale z czego to wynika:
\(\displaystyle{ 2 ^{26} ≡4(\mod 6)}\)
Można to jakoś rozpisać?
Awatar użytkownika
Psiaczek
Użytkownik
Użytkownik
Posty: 1502
Rejestracja: 22 lis 2010, o 09:53
Płeć: Mężczyzna
Lokalizacja: Polska, Warmia, Olsztyn :)
Podziękował: 1 raz
Pomógł: 475 razy

Re: Szybkie potęgowanie modularne.

Post autor: Psiaczek »

rozpisywać można ale to overkill jest chyba ;)

\(\displaystyle{ 2^{26}=2p}\) oraz \(\displaystyle{ 2^{26}=3q+1}\) stąd mnożąc pierwsze przez \(\displaystyle{ 3}\), drugie przez \(\displaystyle{ 2}\)

\(\displaystyle{ 3 \cdot 2^{26}=6 \cdot p}\) oraz \(\displaystyle{ 2 \cdot 2^{26}=6 \cdot q+2}\)

odejmując drugie od pierwszego \(\displaystyle{ 2^{26}=6 \cdot (p-q)-2=6 \cdot (p-q+1)+4}\)
cubasa
Użytkownik
Użytkownik
Posty: 9
Rejestracja: 24 paź 2019, o 12:03
Płeć: Mężczyzna
wiek: 35
Podziękował: 3 razy

Re: Szybkie potęgowanie modularne.

Post autor: cubasa »

Sorry, ale nie kumam. Na wykładach nie miałem takiej metody, o której piszesz.

Czyli jest na to jakiś gotowy wzór lub sposób postępowania, aby tego nie rozpisywać tak jak tutaj:

\(\displaystyle{ 3 ^{17} \pmod{5}=((3 ^{4} ) ^{4} ⋅3)\pmod{5}=((81) ^{4} ⋅3)\pmod{5}=((1) ^{4} ⋅3)\pmod{5}=(1⋅3)\pmod{5}=3\pmod{5}=3.}\)

Dodano po 1 dniu 2 godzinach 27 minutach 13 sekundach:
Czy ktoś pomoże?
Ostatnio zmieniony 3 lis 2019, o 20:09 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Szybkie potęgowanie modularne.

Post autor: Premislav »

Można to trochę usprawnić kosztem użycia teorii: ponieważ \(\displaystyle{ \NWD(3,5)=1}\) i liczba \(\displaystyle{ 5}\) jest pierwsza, więc na mocy małego twierdzenia Fermata mamy \(\displaystyle{ 3^{4}\equiv 1\pmod{5}}\) i \(\displaystyle{ 3^{17}=\left(3^{4}\right)^{4}\cdot 3\equiv 1^{4}\cdot 3\pmod{5}}\).
Jeśli zaś mamy obliczyć \(\displaystyle{ a^{b}\pmod{c}}\), gdzie \(\displaystyle{ c}\) nie jest liczbą pierwszą, za to \(\displaystyle{ \NWD(a,c)=1}\), to przydaje się czasem twierdzenie Eulera:

Kod: Zaznacz cały

https://pl.wikipedia.org/wiki/Twierdzenie_Eulera_%28teoria_liczb%29


Czy to overkill? Może. Kwestia gustu.

A na konkursie w gimnazjum to robiło się tak (tj. ja nie robiłem przeważnie, bo w ogóle nie ogarniałem teorii liczb):
rozpisujemy na pałę kilka przypadków aż do zapętlenia i mamy
\(\displaystyle{ 3^{1}\equiv 3\pmod{5}\\3^{2}\equiv 4\pmod{5}\\3^{3}\equiv 2\pmod{5}\\3^{4}\equiv 1\pmod{5}}\). No to teraz z zapętlenia wynika, że \(\displaystyle{ 3^{4k+1}\equiv 3\pmod{5}}\) dla \(\displaystyle{ k\in \NN}\) (formalnie trzeba by to wykazać indukcyjnie lub zrobić podobny rachunek, co Ty poprzednio, tylko „zewnętrzny" wykładnik \(\displaystyle{ 4}\) zastąpić przez \(\displaystyle{ k}\)).
ODPOWIEDZ