Kalkulator Potęgowania Modularnego

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

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:

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

Jak korzystać z kalkulatora potęgowania modularnego

1. 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.
2. 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).
3. 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.
4. Kliknij Oblicz: Kalkulator obliczy a^b mod n za pomocą potęgowania binarnego i natychmiast wyświetli wynik.
5. 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.
6. 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