Калькулятор піднесення до степеня за модулем

Q: Як обчислити степінь за модулем m вручну?

Скористайтеся методом «квадруй та множ». Спершу зведіть основу: замініть b на b bmod m. Далі запишіть показник у двійковій системі та пословно квадруйте основу, щоразу зводячи результат за модулем m: b^2, b^4, b^8, b^16, ldots. Наприкінці перемножте лише ті значення, що відповідають одиничним бітам показника, зводячи добуток за модулем m після кожного кроку. Так усі проміжні числа залишатимуться меншими за m^2.

Q: Чому результат b^e mod m завжди лежить між 0 і m-1?

Тому що модульна арифметика працює з найменшими невід’ємними лишками. Вираз b^e bmod m за означенням — це остача від ділення b^e на m, а остачі ділення завжди задовольняють умову 0 ≤ c ≤ m-1. Навіть якщо основа від’ємна, її спершу замінюють на еквівалентну додатну остачу, тож відповідь ніколи не буде від’ємною.

Q: Яка остання цифра великого степеня (наприклад, 7^100)?

Це піднесення до степеня за модулем у прихованому вигляді: остання цифра числа — це саме число за модулем 10. Тому обчисліть тут 7^100 bmod 10. Аналогічно, дві останні цифри — це значення за модулем 100, а три останні — за модулем 1000. Це класичний прийом для олімпіадних і домашніх задач про останні цифри.

Q: Що буде, якщо показник степеня дорівнює 0, а модуль — 1?

При e = 0 результат дорівнює 1 bmod m, що дає 1 для будь-якого модуля, крім m = 1, коли результат дорівнює 0 — адже будь-яке ціле число конгруентне 0 за модулем 1. Ці граничні випадки опрацьовано коректно: m = 1 завжди повертає 0 для будь-яких основи і показника, і це математично правильна відповідь, а не помилка.

Q: Чи можна використати від’ємну основу або від’ємний показник?

Від’ємні основи цілком припустимі: калькулятор спершу зводить їх до еквівалентної додатної остачі, тож -12 поводиться як m - 12. Від’ємні показники не підтримуються, оскільки вони вимагали б модульного оберненого основи, яке існує лише за умови gcd(b, m) = 1. Обійти це можна так: спершу знайдіть b^-1 bmod m, а потім піднесіть це число до степеня |e|.

Q: Як піднесення до степеня за модулем застосовується в RSA і криптографії?

Шифрування та розшифрування RSA — це одне піднесення до степеня c = m^e bmod n із модулем на 2048+ бітів, і саме його метод «квадруй та множ» обчислює ефективно. Обмін ключами Діффі–Геллмана та схема Ель-Гамаля працюють так само. Швидкість O(log e) робить величезні показники здійсненними, а складність зворотної операції без секретного ключа забезпечує безпеку цих схем.

Q: Яка типова помилка під час обчислення b^e mod m?

Найпоширеніша помилка — спершу обчислити b^e, а остачу шукати потім: степінь стрімко зростає до астрономічних розмірів і або переповнює калькулятор, або її неможливо записати. Замість цього завжди зводьте результат за модулем m після кожного квадрування і множення. Ще одна часта халепа — забути, що b^0 bmod 1 = 0, а не 1, адже за модулем 1 усе конгруентне 0.

Оновлено: 14.10.2026

Миттєво обчислює b^e mod m, навіть якщо показник має сотні цифр, — за допомогою швидкого методу «квадруй та множ». Введіть основу, невід’ємний показник степеня та додатний модуль; за бажанням можна побачити кожен крок послідовного квадрування.

Піднесення до степеня за модулем

Основа (b)

Будь-яке ціле число, додатне або від’ємне

Показник степеня (e)

Невід’ємне ціле число; може бути настільки великим, що bᵉ неможливо обчислити безпосередньо

Модуль (m)

Додатне ціле число

Показати кроки повторного піднесення до квадрата

Рахувати автоматичноЯкщо увімкнено, результат оновлюватиметься автоматично після зміни будь-якого значення.

Ваші результати

Результат (bᵉ mod m)bᵉ mod m

Приведена основа (b mod m)b mod m

Кроки повторного піднесення до квадрата

Формула піднесення до степеня за модулем

Формула

\[ 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} \]

Де:

\(b\) — основа (будь-яке ціле число)
\(e\) — показник степеня (невід’ємне ціле число)
\(m\) — модуль (додатне ціле число)
\(e_k\) — біти числа \(e\) у двійковому записі
\(c\) — результат: остача від ділення \(b^e\) на \(m\)

Перший рядок — це саме означення піднесення до степеня за модулем. Другий рядок містить тотожність «квадруй та множ» (двійкового піднесення до степеня), на якій працює калькулятор: показник розкладається на степені двійки, значення \(b^{2^k}\) знаходяться послідовним квадруванням, а перемножуються лише ті з них, що відповідають одиничним бітам — і все це за модулем \(m\), тож проміжні числа ніколи не «вибухають» до астрономічних розмірів.

Піднесення до степеня за модулем — приклад обчислення

Приклад: обчислимо \(3^{644} \bmod 645\) — це стандартні значення калькулятора. Число \(3^{644}\) має 308 цифр, тож спершу обчислити степінь, а вже потім знайти остачу — безнадійна ідея.

Крок 1 — зведемо основу: \(3 \bmod 645 = 3\).

Крок 2 — запишемо показник у двійковій системі:

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

Послідовне квадрування за модулем 645 для одиничних бітів дає \(3^4 \equiv 81\), \(3^{128} \equiv 396\) та \(3^{512} \equiv 111 \pmod{645}\).

Крок 3 — перемножимо ці значення, щоразу зводячи результат за модулем 645:

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

Результат: \(3^{644} \bmod 645 = 36\). Алгоритму знадобилося лише 9 квадрувань і 3 множення — 12 модульних операцій замість 643, яких потребував би найпростіший підхід.

Як користуватися калькулятором

Введіть основу (b) — будь-яке ціле число, додатне або від’ємне.
Введіть показник степеня (e) — невід’ємне ціле число. Він може бути настільки великим, що \(b^e\) неможливо обчислити напряму; саме для таких випадків і створено цей інструмент.
Введіть модуль (m) — будь-яке додатне ціле число.
Залиште позначку показувати кроки послідовного квадрування, якщо хочете побачити двійковий запис показника і таблицю всіх кроків квадрування; зніміть її, щоб отримати лише відповідь.
Ознайомтеся з результатом (bᵉ mod m), зведеною основою (b mod m) і покроковим розв’язанням.

Що таке піднесення до степеня за модулем?

Піднесення до степеня за модулем відповідає на питання: яка остача при діленні \(b^e\) на \(m\)? Результат завжди лежить між \(0\) і \(m-1\). Інакше кажучи, це число \(c\), для якого \(0 \le c < m\) і \(b^e \equiv c \pmod{m}\). Наприклад, тотожність \(3^{644} \bmod 645 = 36\) означає, що число \(3^{644}\) при діленні на 645 дає остачу 36.

Найпростіший шлях — обчислити \(b^e\), а потім знайти остачу — дуже швидко заходить у глухий кут. \(3^{644}\) вже має 308 цифр, а в криптографії регулярно використовують показники з сотнями цифр: у такому разі \(b^e\) мало б більше цифр, ніж атомів у Всесвіті. Розв’язок — метод «квадруй та множ»: записуємо показник у двійковій системі, послідовно квадруємо зі зведенням за модулем, щоб отримати \(b^{2^k} \bmod m\), і перемножуємо лише значення для одиничних бітів. Це потребує лише \(O(\log e)\) модульних множень замість \(e-1\), а оскільки кожен проміжний результат зводиться за модулем \(m\), жодне число ніколи не перевищує приблизно \(m^2\).

Піднесення до степеня за модулем — робоча конячка криптографії з відкритим ключем. Шифрування і розшифрування RSA — це одне піднесення до степеня за модулем із дуже великим модулем; на ньому ж будуються обмін ключами Діффі–Геллмана і схема Ель-Гамаля. Він також лежить в основі тестів простоти, як-от тести Ферма і Міллера–Рабіна, які перевіряють умову \(a^{n-1} \equiv 1 \pmod n\) — глибшу теорію можна вивчити за допомогою наших калькуляторів малої теореми Ферма та теореми Ейлера.

Показ кроків робить алгоритм прозорим: у таблиці навпроти кожної позиції біта \(k\) показника стоїть відповідне \(b^{2^k} \bmod m\), виділені рядки — ті, що реально використовуються, а їхній добуток (зведений за модулем \(m\)) і є вашою відповіддю. Саме так це роблять системи комп’ютерної алгебри, і одного погляду на процес достатньо, щоб зрозуміти, чому величезні показники обчислюються так дешево.

Припущення, обмеження та поради

Показник степеня має бути невід’ємним. Від’ємний показник вимагав би модульного оберненого числа \(b\), яке існує лише за умови \(\gcd(b, m) = 1\). Щоб опрацювати такий випадок, спершу знайдіть обернене число нашим калькулятором оберненого за модулем, а потім використайте його результат як основу з додатним показником.
Модуль має бути додатним. Якщо \(m = 1\), будь-яке ціле число конгруентне 0, тож результат дорівнює 0 — це математично коректно, а не помилка.
Від’ємні основи — не проблема. Основу спершу зводиться до найменшого невід’ємного лишку \(b \bmod m\), тому \(-12\) і \(m - 12\) дають ту саму відповідь.
Показник 0 дає \(1 \bmod m\) (що дорівнює 0 лише при \(m = 1\)), у відповідності з \(b^0 = 1\).
Обмеження на розмір: основа і модуль можуть мати до 1000 цифр кожен, а показник — досягати \(10^{18}\). Оскільки алгоритм логарифмічний за показником, навіть такі значення обчислюються миттєво.
Перевіряйте відповідь іншим шляхом: для складеного модуля обчислення можна розбити на частини за степенями простих чисел і потім скомбінувати результати — спробуйте наш калькулятор китайської теореми про остачі, щоб незалежно перевірити результат.

Часті запитання

Як обчислити степінь за модулем m вручну?

Скористайтеся методом «квадруй та множ». Спершу зведіть основу: замініть b на \(b \bmod m\). Далі запишіть показник у двійковій системі та пословно квадруйте основу, щоразу зводячи результат за модулем m: \(b^2, b^4, b^8, b^{16}, \ldots\). Наприкінці перемножте лише ті значення, що відповідають одиничним бітам показника, зводячи добуток за модулем m після кожного кроку. Так усі проміжні числа залишатимуться меншими за \(m^2\).

Чому результат b^e mod m завжди лежить між 0 і m-1?

Тому що модульна арифметика працює з найменшими невід’ємними лишками. Вираз \(b^e \bmod m\) за означенням — це остача від ділення \(b^e\) на \(m\), а остачі ділення завжди задовольняють умову \(0 \le c \le m-1\). Навіть якщо основа від’ємна, її спершу замінюють на еквівалентну додатну остачу, тож відповідь ніколи не буде від’ємною.

Яка остання цифра великого степеня (наприклад, 7^100)?

Це піднесення до степеня за модулем у прихованому вигляді: остання цифра числа — це саме число за модулем 10. Тому обчисліть тут \(7^{100} \bmod 10\). Аналогічно, дві останні цифри — це значення за модулем 100, а три останні — за модулем 1000. Це класичний прийом для олімпіадних і домашніх задач про останні цифри.

Що буде, якщо показник степеня дорівнює 0, а модуль — 1?

При \(e = 0\) результат дорівнює \(1 \bmod m\), що дає 1 для будь-якого модуля, крім \(m = 1\), коли результат дорівнює 0 — адже будь-яке ціле число конгруентне 0 за модулем 1. Ці граничні випадки опрацьовано коректно: \(m = 1\) завжди повертає 0 для будь-яких основи і показника, і це математично правильна відповідь, а не помилка.

Чи можна використати від’ємну основу або від’ємний показник?

Від’ємні основи цілком припустимі: калькулятор спершу зводить їх до еквівалентної додатної остачі, тож \(-12\) поводиться як \(m - 12\). Від’ємні показники не підтримуються, оскільки вони вимагали б модульного оберненого основи, яке існує лише за умови \(\gcd(b, m) = 1\). Обійти це можна так: спершу знайдіть \(b^{-1} \bmod m\), а потім піднесіть це число до степеня \(|e|\).

Як піднесення до степеня за модулем застосовується в RSA і криптографії?

Шифрування та розшифрування RSA — це одне піднесення до степеня \(c = m^e \bmod n\) із модулем на 2048+ бітів, і саме його метод «квадруй та множ» обчислює ефективно. Обмін ключами Діффі–Геллмана та схема Ель-Гамаля працюють так само. Швидкість \(O(\log e)\) робить величезні показники здійсненними, а складність зворотної операції без секретного ключа забезпечує безпеку цих схем.

Яка типова помилка під час обчислення b^e mod m?

Найпоширеніша помилка — спершу обчислити \(b^e\), а остачу шукати потім: степінь стрімко зростає до астрономічних розмірів і або переповнює калькулятор, або її неможливо записати. Замість цього завжди зводьте результат за модулем m після кожного квадрування і множення. Ще одна часта халепа — забути, що \(b^0 \bmod 1 = 0\), а не 1, адже за модулем 1 усе конгруентне 0.