Kalkulator Potęgowania Modularnego

Obliczaj potęgowanie modularne a^b mod n efektywnie, używając algorytmu binarnego potęgowania (szybkiego potęgowania). Wprowadź podstawę, wykładnik i moduł, aby uzyskać natychmiastowe wyniki z rozbiciem krok po kroku na metodę potęgowania i mnożenia, wizualizację rozkładu binarnego oraz kontekst kryptograficzny.

Embed Kalkulator Potęgowania Modularnego Widget

O Kalkulator Potęgowania Modularnego

Kalkulator potęgowania modularnego oblicza \(a^b \bmod n\) — podnosząc podstawę \(a\) do wykładnika \(b\) i wyznaczając resztę z dzielenia przez moduł \(n\). Wykorzystuje on algorytm potęgowania binarnego (zwany również szybkim potęgowaniem lub potęgowaniem przez kwadratowanie), który redukuje operację z \(O(b)\) mnożeń do zaledwie \(O(\log b)\). Jest to ten sam algorytm, który jest stosowany w rzeczywistych implementacjach kryptograficznych, takich jak RSA, Diffie-Hellman i ElGamal.

Zastosowania potęgowania modularnego

🔐

Szyfrowanie RSA

Szyfrowanie i deszyfrowanie wiadomości przy użyciu potęgowania modularnego z iloczynami dużych liczb pierwszych

🤝

Diffie-Hellman

Protokół wymiany kluczy obliczający g^a mod p dla bezpiecznych wspólnych sekretów

✍

Podpisy cyfrowe

DSA, ECDSA i EdDSA opierają się na potęgowaniu modularnym

🧪

Testowanie pierwszości

Testy Fermata i Millera-Rabina używają a^(n-1) mod n do sprawdzania pierwszości

🏆

Programowanie konkurencyjne

Arytmetyka modularna z szybkim potęgowaniem jest niezbędna w zadaniach konkursowych

🔗

Blockchain

Proof-of-work i haszowanie kryptograficzne opierają się na arytmetyce modularnej

Jak działa algorytm potęgowania binarnego

Kluczową obserwacją jest to, że każdy wykładnik możemy rozłożyć na sumę potęg liczby 2, korzystając z jego reprezentacji binarnej. Na przykład, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), więc \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

Algorytm przetwarza cyfry binarne wykładnika od lewej do prawej:

Krok 1: Zamień wykładnik \(b\) na postać binarną.

Krok 2: Zainicjuj wynik = 1 (lub = podstawa, jeśli pierwszy bit wynosi 1).

Krok 3: Dla każdego kolejnego bitu: Podnieś do kwadratu wynik (mod n). Jeśli bit wynosi 1, również pomnóż przez podstawę (mod n).

Krok 4: Po przetworzeniu wszystkich bitów, wynik to \(a^b \bmod n\).

Pseudokod

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // bit wynosi 1
            result = (result × base) mod mod
        exp = exp >> 1        // przesunięcie w prawo (dzielenie przez 2)
        base = (base × base) mod mod
    return result

Kluczowe wzory

Właściwość	Wzór	Opis
Potęgowanie modularne	\(a^b \bmod n\)	Reszta z dzielenia a^b przez n
Małe Twierdzenie Fermata	\(a^{p-1} \equiv 1 \pmod{p}\)	Dla liczby pierwszej p i nwd(a,p)=1
Twierdzenie Eulera	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	Dla nwd(a,n)=1, gdzie φ to funkcja Eulera
Złożoność metody binarnej	\(O(\log b)\) mnożeń	Maksymalnie 2·log₂(b) mnożeń modularnych
Szyfrowanie RSA	\(c = m^e \bmod n\)	Szyfrowanie wiadomości m kluczem publicznym (e, n)
Deszyfrowanie RSA	\(m = c^d \bmod n\)	Deszyfrowanie szyfrogramu c kluczem prywatnym d

Jak korzystać z kalkulatora potęgowania modularnego

Wprowadź podstawę (a): Jest to liczba, którą chcesz podnieść do potęgi. Może być dodatnia lub ujemna. Na przykład wpisz 7, aby obliczyć 7^256 mod 13.
Wprowadź wykładnik (b): Musi to być nieujemna liczba całkowita. Reprezentuje potęgę. W zastosowaniach kryptograficznych może być bardzo duży (kalkulator obsługuje do 10^18).
Wprowadź moduł (n): Musi to być dodatnia liczba całkowita. Jest to liczba, przez którą dzielisz, aby otrzymać resztę. W RSA jest to zazwyczaj iloczyn dwóch dużych liczb pierwszych.
Kliknij Oblicz: Kalkulator obliczy a^b mod n za pomocą potęgowania binarnego i natychmiast wyświetli wynik.
Obejrzyj animację: Naciśnij Odtwórz, aby zobaczyć, jak algorytm potęgowania binarnego wykonuje się krok po kroku. Każdy bit wykładnika jest przetwarzany po kolei, pokazując, czy algorytm wykonuje kwadratowanie, czy kwadratowanie i mnożenie.
Przejrzyj śledzenie: Tabela krok po kroku pokazuje każde obliczenie pośrednie, a porównanie wydajności pokazuje, o ile szybsze jest potęgowanie binarne w porównaniu z naiwnym, powtarzanym mnożeniem.

Dlaczego potęgowanie binarne jest szybkie

Rozważmy obliczenie \(2^{1000} \bmod 13\). Naiwne podejście wymagałoby 999 mnożeń. Potęgowanie binarne zamienia 1000 na postać binarną (1111101000), która ma 10 bitów. Wymaga maksymalnie 9 potęgowań do kwadratu plus kilka mnożeń dla każdego bitu „1” — łącznie około 15 operacji. To o około 98,5% mniej operacji. W przypadku wykładników o skali kryptograficznej z setkami cyfr różnica jest astronomiczna: metoda binarna zajmuje tysiące operacji, podczas gdy metoda naiwna wymagałaby więcej operacji niż jest atomów we wszechświecie.

FAQ

Co to jest potęgowanie modularne?

Potęgowanie modularne oblicza (a^b) mod n — podnosi podstawę do wykładnika, a następnie wyznacza resztę z dzielenia przez moduł. Jest to podstawowa operacja w kryptografii klucza publicznego (RSA, Diffie-Hellman, ElGamal) i jest szeroko stosowana w teorii liczb, programowaniu konkurencyjnym i informatyce. Metoda potęgowania binarnego oblicza to efektywnie w czasie O(log b) mnożeń.

Jak działa potęgowanie binarne (potęgowanie przez kwadratowanie)?

Potęgowanie binarne zamienia wykładnik na jego reprezentację binarną, a następnie przetwarza każdy bit od lewej do prawej (lub od prawej do lewej). Dla każdego bitu podnosi aktualny wynik do kwadratu modulo n. Jeśli bit wynosi 1, dodatkowo mnoży wynik przez podstawę modulo n. Zmniejsza to liczbę mnożeń z b−1 (metoda naiwna) do maksymalnie 2×log₂(b), co umożliwia obliczenia z ogromnymi wykładnikami.

Dlaczego potęgowanie modularne jest ważne w kryptografii?

Szyfrowanie RSA oblicza c = m^e mod n dla szyfrowania i m = c^d mod n dla deszyfrowania, gdzie n jest iloczynem dwóch dużych liczb pierwszych, a wykładniki mogą mieć setki cyfr długości. Bez szybkiego potęgowania modularnego operacje te byłyby obliczeniowo niemożliwe. Bezpieczeństwo opiera się na fakcie, że operacja odwrotna (obliczanie logarytmu dyskretnego) jest uważana za obliczeniowo niewykonalną.

Czy podstawa może być ujemna?

Tak, ujemne podstawy są w pełni obsługiwane. Kalkulator najpierw redukuje podstawę modulo n (używając arytmetyki modularnej Pythona, która zawsze zwraca nieujemny wynik dla dodatniego n). Na przykład, (−3)^2 mod 7 = 9 mod 7 = 2. Wyniki ujemne nigdy nie wystąpią, ponieważ redukcja modularna zawsze daje wartość w zakresie [0, n−1].

Co się dzieje, gdy moduł wynosi 1?

Dowolna liczba całkowita modulo 1 równa się 0. Wynika to z faktu, że dzielenie dowolnej liczby całkowitej przez 1 daje tę samą liczbę z resztą 0. Zatem a^b mod 1 = 0 dla wszystkich wartości a i b. Kalkulator traktuje to jako przypadek specjalny.

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Kalkulator Potęgowania Modularnego" na https://MiniWebtool.com/pl/kalkulator-potegowania-modularnego/ z MiniWebtool, https://MiniWebtool.com/

autor: zespół miniwebtool. Aktualizacja: 2026-04-16

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.

Inne powiązane narzędzia:

Kalkulator Wartości BezwzględnejNowy

Sprawdzacz Liczb ZaprzyjaźnionychNowy

Wizualizator Przeniesień i PożyczekNowy

Kalkulator chińskiego twierdzenia o resztach

Kalkulator sześcianu i pierwiastka sześciennego

Kalkulator Pierwiastka Sześciennego

Kalkulator Funkcji Tocjenta Eulera

Kalkulator modularnej odwrotności multiplikatywnej

Kalkulator Rozkładu na Czynniki Pierwsze

Kalkulator Pierwiastka Pierwotnego

Kalkulator Potęgowania Modularnego

O Kalkulator Potęgowania Modularnego

Zastosowania potęgowania modularnego

Jak działa algorytm potęgowania binarnego

Pseudokod

Kluczowe wzory

Jak korzystać z kalkulatora potęgowania modularnego

Dlaczego potęgowanie binarne jest szybkie

FAQ

Inne powiązane narzędzia:

Zaawansowane działania matematyczne:

Polecane narzędzia: