Natychmiast oblicz potęgowanie modularne xy mod n. Wprowadź podstawę, wykładnik i moduł, aby sprawnie wyznaczyć resztę za pomocą algorytmu potęgowania binarnego.
Kalkulator potęgowania modularnego
Jak korzystać z kalkulatora
- W polu x (podstawa) wpisz podstawę będącą liczbą całkowitą.
- W polu y (wykładnik) wpisz nieujemny wykładnik całkowity.
- W polu n (moduł) wpisz dodatni moduł całkowity (n ≥ 1).
- Wybierz Oblicz. Wartość xy mod n pojawi się w polu Wynik.
- Aby rozpocząć nowe obliczenie, wybierz Wyczyść.
Czym jest potęgowanie modularne?
Potęgowanie modularne wyznacza resztę z dzielenia xy przez n:
xy mod n = r
gdzie r jest resztą z dzielenia xy przez n i spełnia warunek 0 ≤ r < n.
Ta operacja ma podstawowe znaczenie w teorii liczb oraz kryptografii klucza publicznego (w tym RSA), gdzie bardzo duże potęgi trzeba obliczać wydajnie.
Szybkie potęgowanie modularne
Bezpośrednie obliczanie xy staje się niepraktyczne przy dużych wykładnikach. Algorytm potęgowania binarnego rozwiązuje ten problem w O(log y) operacjach przez kolejne podnoszenie podstawy do kwadratu:
- Jeśli y jest parzyste: xy = (xy/2)2
- Jeśli y jest nieparzyste: xy = x × xy−1
Moduł jest stosowany na każdym etapie, dzięki czemu wartości pośrednie pozostają małe.
Przykłady potęgowania modularnego
| x (podstawa) | y (wykładnik) | n (moduł) | xy mod n |
|---|---|---|---|
| 2 | 10 | 7 | 2 |
| 3 | 4 | 5 | 1 |
| 5 | 3 | 13 | 8 |
| 7 | 0 | 10 | 1 |
| 2 | 100 | 1000000007 | 976371285 |
Najczęściej zadawane pytania
Czym jest potęgowanie modularne?
Potęgowanie modularne oblicza xy mod n, czyli resztę z dzielenia xy przez n. Ma podstawowe znaczenie w kryptografii i teorii liczb.
Jak obliczyć xy mod n?
Wprowadź podstawę x, wykładnik y i moduł n, a następnie wybierz Oblicz. Wynikiem jest reszta z dzielenia xy przez n, obliczona za pomocą szybkiego potęgowania modularnego.
Dlaczego potęgowanie modularne jest stosowane w kryptografii?
Potęgowanie modularne stanowi podstawę RSA i protokołu Diffiego-Hellmana. Obliczenie wprost jest wydajne, ale odwrócenie go jest niezwykle trudne ze względu na problem logarytmu dyskretnego. Ta asymetria jest użyteczna w bezpieczeństwie cyfrowym.
Ile wynosi 2¹⁰ mod 7?
2¹⁰ = 1024, a 1024 = 146 × 7 + 2. Zatem 2¹⁰ mod 7 = 2.
Czym jest algorytm potęgowania binarnego?
To wydajna metoda obliczania xy mod n przez kolejne dzielenie wykładnika przez dwa. Liczba operacji maleje z O(y) do O(log y), dzięki czemu ogromne potęgi można przetwarzać w ułamku sekundy.
Powiązane kalkulatory i poradniki
