Kalkulator potęgowania modularnego

Q: Jak obliczyć potęgę modulo m na papierze?

Użyj metody kwadratów i mnożeń. Najpierw zredukuj podstawę: zamień b na b bmod m. Następnie zapisz wykładnik w systemie dwójkowym i wielokrotnie podnoś podstawę do kwadratu, redukując modulo m po każdym kroku: b^2, b^4, b^8, b^16, ldots. Na koniec pomnóż przez siebie tylko te wartości, które odpowiadają bitom 1 wykładnika, za każdym razem redukując modulo m. Dzięki temu każda liczba pośrednia pozostaje poniżej m^2.

Q: Dlaczego wynik b^e mod m zawsze mieści się między 0 a m-1?

Ponieważ arytmetyka modularna operuje na najmniejszych nieujemnych resztach. Wyrażenie b^e bmod m jest z definicji resztą z dzielenia b^e przez m, a reszty z dzielenia zawsze spełniają 0 ≤ c ≤ m-1. Nawet gdy podstawa jest ujemna, jest ona najpierw zamieniana na równoważną dodatnią resztę, więc wynik nigdy nie jest ujemny.

Q: Jaka jest ostatnia cyfra dużej potęgi (np. 7^100)?

To potęgowanie modularne w przebraniu: ostatnia cyfra liczby to ta liczba modulo 10. Wystarczy więc obliczyć tu 7^100 bmod 10. Podobnie dwie ostatnie cyfry to wartość modulo 100, a trzy ostatnie — modulo 1000. To klasyczna droga na skróty w zadaniach olimpijskich i domowych dotyczących końcowych cyfr.

Q: Co się dzieje, gdy wykładnik wynosi 0 albo moduł wynosi 1?

Przy e = 0 wynikiem jest 1 bmod m, czyli 1 dla każdego modułu poza m = 1, gdzie wynosi 0 — ponieważ każda liczba całkowita jest przystająca do 0 modulo 1. Te przypadki brzegowe są obsłużone poprawnie: m = 1 zawsze zwraca 0 dla dowolnej podstawy i wykładnika, co jest matematycznie prawidłowe, a nie błędem.

Q: Czy mogę użyć ujemnej podstawy lub ujemnego wykładnika?

Ujemne podstawy nie stanowią problemu: kalkulator najpierw redukuje je do równoważnej dodatniej reszty, więc -12 zachowuje się jak m - 12. Ujemne wykładniki nie są obsługiwane, ponieważ wymagałyby odwrotności modularnej podstawy, a ta istnieje tylko wtedy, gdy gcd(b, m) = 1. Możesz to obejść: najpierw znajdź b^-1 bmod m, a następnie podnieś ją do potęgi |e|.

Q: Jak potęgowanie modularne jest wykorzystywane w RSA i kryptografii?

Szyfrowanie i deszyfrowanie RSA to za każdym razem pojedyncze potęgowanie modularne c = m^e bmod n z modułem o rozmiarze co najmniej 2048 bitów — i dokładnie tę operacjęB wydajnie oblicza metoda kwadratów i mnożeń. Tak samo działa wymiana kluczy Diffiego–Hellmana i ElGamal. Szybkość rzędu O(log e) czyni ogromne wykładniki wykonalnymi, a trudność odwrócenia tej operacji bez tajnego klucza zapewnia bezpieczeństwo tych schematów.

Q: Jaki jest częsty błąd przy obliczaniu b^e mod m?

Najczęstszy błąd to obliczenie najpierw b^e, a dopiero potem wzięcie reszty — potęga błyskawicznie rośnie do astronomicznych rozmiarów i albo przekracza możliwości kalkulatora, albo nie da się jej zapisać. Zamiast tego zawsze redukuj modulo m po każdym podniesieniu do kwadratu i każdym mnożeniu. Innym częstym potknięciem jest zapominanie, że b^0 bmod 1 = 0, a nie 1, ponieważ modulo 1 wszystko jest przystające do 0.

Zaktualizowano: 14 października 2026

Błyskawicznie oblicza b^e mod m, nawet gdy wykładnik ma setki cyfr, wykorzystując szybkie potęgowanie metodą kwadratów i mnożeń. Wpisz podstawę, nieujemny wykładnik i dodatni moduł, a opcjonalnie zobacz każdy krok potęgowania przez podwajanie.

Obliczanie potęgi modulo m

Wzór na potęgowanie modularne

Wzór

\[ c \;=\; b^e \bmod m \] \[ e = \sum_{k=0}^{n} e_k\,2^k \;\;\Longrightarrow\;\; b^e \;\equiv\; \prod_{k:\; e_k = 1} \bigl(b^{2^k} \bmod m\bigr) \pmod{m}, \qquad b^{2^k} \equiv \bigl(b^{2^{k-1}}\bigr)^2 \pmod{m} \]

gdzie:

\(b\) — podstawa (dowolna liczba całkowita)
\(e\) — wykładnik (nieujemna liczba całkowita)
\(m\) — moduł (dodatnia liczba całkowita)
\(e_k\) — bity liczby \(e\) w jej zapisie dwójkowym
\(c\) — wynik: reszta z dzielenia \(b^e\) przez \(m\)

Pierwszy wzór to definicja potęgowania modularnego. Drugi przedstawia tożsamość wykorzystywaną przez kalkulator w metodzie kwadratów i mnożeń (potęgowaniu dwójkowym): wykładnik jest rozkładany na potęgi dwójki, potęgi \(b^{2^k}\) wyznaczane są przez wielokrotne podnoszenie do kwadratu, a mnożone są tylko te z nich, które odpowiadają ustawionym bitom — wszystko modulo \(m\), dzięki czemu liczby pośrednie nigdy nie rozrastają się do gigantycznych rozmiarów.

Potęgowanie modularne – przykład obliczenia

Przykład: oblicz \(3^{644} \bmod 645\) — to domyślne wartości kalkulatora. Liczba \(3^{644}\) ma 308 cyfr, więc najpierw policzyć potęgę, a dopiero potem zredukować, nie ma najmniejszego sensu.

Krok 1 — zredukuj podstawę: \(3 \bmod 645 = 3\).

Krok 2 — zapisz wykładnik w systemie dwójkowym:

\[ 644 = 512 + 128 + 4 = 1010000100_2 \]

Wielokrotne podnoszenie do kwadratu modulo 645 daje dla ustawionych bitów: \(3^4 \equiv 81\), \(3^{128} \equiv 396\) oraz \(3^{512} \equiv 111 \pmod{645}\).

Krok 3 — pomnóż te wartości, za każdym razem redukując modulo 645:

\[ 3^{644} \equiv 81 \times 396 \times 111 \equiv 471 \times 111 \equiv 52281 \equiv 36 \pmod{645} \]

Wynik: \(3^{644} \bmod 645 = 36\). Algorytm wymagał tylko 9 podniesień do kwadratu i 3 mnożeń — 12 działań modularnych zamiast 643, których potrzebowałoby naiwne podejście.

Jak korzystać z kalkulatora

Wpisz podstawę (b) — dowolną liczbę całkowitą, dodatnią lub ujemną.
Wpisz wykładnik (e) — nieujemną liczbę całkowitą. Może być tak duży, że \(b^e\) nie da się obliczyć wprost; dokładnie do takich przypadków służy to narzędzie.
Wpisz moduł (m) — dowolną dodatnią liczbę całkowitą.
Zostaw zaznaczone pole Pokaż kroki potęgowania przez podwajanie, jeśli chcesz zobaczyć zapis dwójkowy wykładnika i tabelę każdego kroku podnoszenia do kwadratu; odznacz je, aby otrzymać sam wynik.
Odczytaj wynik (bᵉ mod m), zredukowaną podstawę (b mod m) oraz obliczenia krok po kroku.

Czym jest potęgowanie modularne?

Potęgowanie modularne odpowiada na pytanie: jaka jest reszta z dzielenia \(b^e\) przez \(m\)? Wynik zawsze mieści się między \(0\) a \(m-1\). Inaczej mówiąc, jest to liczba \(c\) spełniająca \(0 \le c < m\), dla której \(b^e \equiv c \pmod{m}\). Na przykład \(3^{644} \bmod 645 = 36\) oznacza, że \(3^{644}\) dzielone przez 645 daje resztę 36.

Naiwna droga — obliczenie \(b^e\), a dopiero potem wzięcie reszty — szybko zawodzi. \(3^{644}\) ma już 308 cyfr, a w kryptografii na co dzień stosuje się wykładniki liczące setki cyfr, przy których \(b^e\) miałoby więcej cyfr niż atomów we Wszechświecie. Rozwiązaniem jest metoda kwadratów i mnożeń: zapisujemy wykładnik w systemie dwójkowym, wyznaczamy \(b^{2^k} \bmod m\) przez wielokrotne podnoszenie do kwadratu z redukcją, a następnie mnożymy tylko wartości odpowiadające ustawionym bitom. Wymaga to zaledwie \(O(\log e)\) mnożeń modularnych zamiast \(e-1\), a ponieważ każdy wynik pośredni jest redukowany modulo \(m\), żadna liczba nie przekracza w przybliżeniu \(m^2\).

Potęgowanie modularne to koń roboczy kryptografii z kluczem publicznym. Szyfrowanie i deszyfrowanie RSA to pojedyncze potęgowanie modularne z ogromnym modułem; opiera się na nim również wymiana kluczy Diffiego–Hellmana i schemat ElGamala. Metoda ta napędza też testy pierwszości, takie jak test Fermata i test Millera–Rabina, które sprawdzają, czy \(a^{n-1} \equiv 1 \pmod n\) — teorię liczb stojącą za tymi testami możesz zgłębić w naszych kalkulatorach małego twierdzenia Fermata i twierdzenia Eulera.

Wyświetlanie kroków czyni algorytm przejrzystym: tabela pokazuje każdą pozycję bitu \(k\) wykładnika obok \(b^{2^k} \bmod m\), pogrubione wiersze to te faktycznie wykorzystane, a ich iloczyn (zredukowany modulo \(m\)) jest szukanym wynikiem. Dokładnie to samo robią wewnętrznie systemy algebry komputerowej, a jednorazowe zobaczenie tego na własne oczy to najlepszy sposób, by zrozumieć, dlaczego ogromne wykładniki są tanie.

Założenia, ograniczenia i wskazówki

Wykładnik musi być nieujemny. Ujemny wykładnik wymagałby odwrotności modularnej \(b\), która istnieje tylko wtedy, gdy \(\gcd(b, m) = 1\). Aby obsłużyć taki przypadek, najpierw znajdź odwrotność naszym kalkulatorem odwrotności modulo, a następnie użyj jej wyniku jako podstawy z dodatnim wykładnikiem.
Moduł musi być dodatni. Jeśli \(m = 1\), każda liczba całkowita jest przystająca do 0, więc wynikiem jest 0 — to poprawny wynik matematyczny, a nie błąd.
Ujemne podstawy są w porządku. Podstawa jest najpierw redukowana do najmniejszej nieujemnej reszty \(b \bmod m\), więc \(-12\) i \(m - 12\) dają ten sam wynik.
Wykładnik 0 daje \(1 \bmod m\) (co równa się 0 tylko przy \(m = 1\)), zgodnie z \(b^0 = 1\).
Ograniczenia rozmiaru: podstawa i moduł mogą mieć do 1000 cyfr każdy, a wykładnik może być tak duży jak \(10^{18}\). Ponieważ algorytm jest logarytmiczny względem wykładnika, nawet taka wartość obliczana jest natychmiast.
Sprawdź wynik inną drogą: dla modułu złożonego możesz rozbić obliczenia na części będące potęgami liczb pierwszych i połączyć je z powrotem — wypróbuj nasz kalkulator chińskiego twierdzenia o resztach, aby zweryfikować wyniki niezależnie.

Najczęściej zadawane pytania

Jak obliczyć potęgę modulo m na papierze?

Użyj metody kwadratów i mnożeń. Najpierw zredukuj podstawę: zamień b na \(b \bmod m\). Następnie zapisz wykładnik w systemie dwójkowym i wielokrotnie podnoś podstawę do kwadratu, redukując modulo m po każdym kroku: \(b^2, b^4, b^8, b^{16}, \ldots\). Na koniec pomnóż przez siebie tylko te wartości, które odpowiadają bitom 1 wykładnika, za każdym razem redukując modulo m. Dzięki temu każda liczba pośrednia pozostaje poniżej \(m^2\).

Dlaczego wynik b^e mod m zawsze mieści się między 0 a m-1?

Ponieważ arytmetyka modularna operuje na najmniejszych nieujemnych resztach. Wyrażenie \(b^e \bmod m\) jest z definicji resztą z dzielenia \(b^e\) przez \(m\), a reszty z dzielenia zawsze spełniają \(0 \le c \le m-1\). Nawet gdy podstawa jest ujemna, jest ona najpierw zamieniana na równoważną dodatnią resztę, więc wynik nigdy nie jest ujemny.

Jaka jest ostatnia cyfra dużej potęgi (np. 7^100)?

To potęgowanie modularne w przebraniu: ostatnia cyfra liczby to ta liczba modulo 10. Wystarczy więc obliczyć tu \(7^{100} \bmod 10\). Podobnie dwie ostatnie cyfry to wartość modulo 100, a trzy ostatnie — modulo 1000. To klasyczna droga na skróty w zadaniach olimpijskich i domowych dotyczących końcowych cyfr.

Co się dzieje, gdy wykładnik wynosi 0 albo moduł wynosi 1?

Przy \(e = 0\) wynikiem jest \(1 \bmod m\), czyli 1 dla każdego modułu poza \(m = 1\), gdzie wynosi 0 — ponieważ każda liczba całkowita jest przystająca do 0 modulo 1. Te przypadki brzegowe są obsłużone poprawnie: \(m = 1\) zawsze zwraca 0 dla dowolnej podstawy i wykładnika, co jest matematycznie prawidłowe, a nie błędem.

Czy mogę użyć ujemnej podstawy lub ujemnego wykładnika?

Ujemne podstawy nie stanowią problemu: kalkulator najpierw redukuje je do równoważnej dodatniej reszty, więc \(-12\) zachowuje się jak \(m - 12\). Ujemne wykładniki nie są obsługiwane, ponieważ wymagałyby odwrotności modularnej podstawy, a ta istnieje tylko wtedy, gdy \(\gcd(b, m) = 1\). Możesz to obejść: najpierw znajdź \(b^{-1} \bmod m\), a następnie podnieś ją do potęgi \(|e|\).

Jak potęgowanie modularne jest wykorzystywane w RSA i kryptografii?

Szyfrowanie i deszyfrowanie RSA to za każdym razem pojedyncze potęgowanie modularne \(c = m^e \bmod n\) z modułem o rozmiarze co najmniej 2048 bitów — i dokładnie tę operacjęB wydajnie oblicza metoda kwadratów i mnożeń. Tak samo działa wymiana kluczy Diffiego–Hellmana i ElGamal. Szybkość rzędu \(O(\log e)\) czyni ogromne wykładniki wykonalnymi, a trudność odwrócenia tej operacji bez tajnego klucza zapewnia bezpieczeństwo tych schematów.

Jaki jest częsty błąd przy obliczaniu b^e mod m?

Najczęstszy błąd to obliczenie najpierw \(b^e\), a dopiero potem wzięcie reszty — potęga błyskawicznie rośnie do astronomicznych rozmiarów i albo przekracza możliwości kalkulatora, albo nie da się jej zapisać. Zamiast tego zawsze redukuj modulo m po każdym podniesieniu do kwadratu i każdym mnożeniu. Innym częstym potknięciem jest zapominanie, że \(b^0 \bmod 1 = 0\), a nie 1, ponieważ modulo 1 wszystko jest przystające do 0.