Калькулятор возведения в степень по модулю
Мгновенно вычисляет b^e mod m, даже если степень состоит из сотен цифр, — методом быстрого возведения в степень (умножением и возведением в квадрат). Введите основание, неотрицательную степень и положительный модуль, а при желании просмотрите все шаги последовательного возведения в квадрат.
Возведение в степень по модулю 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}\) даёт остаток 36 при делении на 645.
Наивный подход — сначала вычислить \(b^e\), а затем взять остаток — очень быстро перестаёт работать. У \(3^{644}\) уже 308 цифр, а в криптографии routinely... в криптографии routinely используются показатели из сотен цифр, при которых \(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 всё сравнимо с нулём.