Witajcie. Chciałbym sobie przypomnieć jak oblicza się reszty z dzielenia dużych liczb przy pomocy małego twierdzenia Fermata, a może innych narzędzi?
Na przykład, jak policzyć
\(\displaystyle{ 7^{13131313}}\) w \(\displaystyle{ \mathbb{Z}_{13}}\) albo \(\displaystyle{ 5^{13579}}\) w \(\displaystyle{ \mathbb{Z}_{11}}\).
Dziękuję i pozdrawiam.
Reszty z dzielenia dużych liczb
- SaxoN
- Użytkownik
- Posty: 154
- Rejestracja: 20 cze 2008, o 14:33
- Płeć: Mężczyzna
- Lokalizacja: Katowice/ Warszawa
- Podziękował: 3 razy
- Pomógł: 9 razy
Reszty z dzielenia dużych liczb
MTF mówi nam, że \(\displaystyle{ a^{p-1}\equiv 1\pmod{p}}\), gdzie \(\displaystyle{ p\in\mathbb{P}}\) oraz \(\displaystyle{ a\neq 0}\). Mamy zatem
\(\displaystyle{ 7^{13131313}=7^{1094276\cdot 12 +1}=\big(7^{12}\big)^{1094276}\cdot 7\equiv 1^{1094276}\cdot7\equiv 7 \pmod{13}}\)
\(\displaystyle{ 5^{13579}=5^{1357\cdot 10+9}=\big(5^{10}\big)^{1357}\cdot 5^9\equiv 5^9\pmod{11}}\)
takie \(\displaystyle{ 5^9}\) możemy sprawnie policzyć jako \(\displaystyle{ \big(5^3\big)^3}\) na przykład
\(\displaystyle{ 7^{13131313}=7^{1094276\cdot 12 +1}=\big(7^{12}\big)^{1094276}\cdot 7\equiv 1^{1094276}\cdot7\equiv 7 \pmod{13}}\)
\(\displaystyle{ 5^{13579}=5^{1357\cdot 10+9}=\big(5^{10}\big)^{1357}\cdot 5^9\equiv 5^9\pmod{11}}\)
takie \(\displaystyle{ 5^9}\) możemy sprawnie policzyć jako \(\displaystyle{ \big(5^3\big)^3}\) na przykład
-
- Użytkownik
- Posty: 93
- Rejestracja: 31 maja 2007, o 17:53
- Płeć: Mężczyzna
- Lokalizacja: Chojnice
- Podziękował: 1 raz
- Pomógł: 3 razy
Reszty z dzielenia dużych liczb
W ogólności do takich obliczeń służy algorytm szybkiego potęgowania modulo, który nie wymaga, aby modulować przez liczbę pierwszą.
... %99gowania
... %99gowania
Reszty z dzielenia dużych liczb
Wiem ze odgrzebuje stary temat, ale nie ma sensu robić nowego, mam dokładnie taki sam problem jak autor z tym ze
Co zrobić jeśli duża liczba nie daje nam dokładnej reszty ? tzn \(\displaystyle{ 7^{13131313}}\) w ciełe \(\displaystyle{ \mathbb{F}_13}\), dzielmy przez \(\displaystyle{ 12}\), jak sakson napisał wychodzi \(\displaystyle{ 1094276,083}\).
W notatkach ze studiów, wykładowca zamiast "\(\displaystyle{ 1094276}\)" wpisał "\(\displaystyle{ 1034276}\)" była na to jakaś metoda której nie pamietam.
To samo np w przykładzie \(\displaystyle{ 2^{365789}}\) w ciele \(\displaystyle{ \mathbb{F}_7}\)
\(\displaystyle{ \frac{365789}{6} = 60964,83333}\) ( notatkach mam zamiast tego wydnieje \(\displaystyle{ 60964 + 5}\) - reszta z dzielenia )
Co zrobić jeśli duża liczba nie daje nam dokładnej reszty ? tzn \(\displaystyle{ 7^{13131313}}\) w ciełe \(\displaystyle{ \mathbb{F}_13}\), dzielmy przez \(\displaystyle{ 12}\), jak sakson napisał wychodzi \(\displaystyle{ 1094276,083}\).
W notatkach ze studiów, wykładowca zamiast "\(\displaystyle{ 1094276}\)" wpisał "\(\displaystyle{ 1034276}\)" była na to jakaś metoda której nie pamietam.
To samo np w przykładzie \(\displaystyle{ 2^{365789}}\) w ciele \(\displaystyle{ \mathbb{F}_7}\)
\(\displaystyle{ \frac{365789}{6} = 60964,83333}\) ( notatkach mam zamiast tego wydnieje \(\displaystyle{ 60964 + 5}\) - reszta z dzielenia )
Ostatnio zmieniony 2 lut 2012, o 20:34 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .
Powód: Nieczytelny zapis - brak LaTeX-a. Proszę zapoznaj się z instrukcją: http://matematyka.pl/latex.htm .