Калькулятор Модульного Возведения в Степень

Эффективно вычисляйте модульное возведение в степень a^b mod n, используя алгоритм бинарного возведения в степень (быстрое возведение в степень). Введите основание, показатель степени и модуль, чтобы получить мгновенные результаты с пошаговым описанием метода возведения в квадрат и умножения, визуализацией двоичного разложения и криптографическим контекстом.

Embed Калькулятор Модульного Возведения в Степень Widget

О Калькулятор Модульного Возведения в Степень

Калькулятор модульного возведения в степень вычисляет \(a^b \bmod n\) — возведение основания \(a\) в степень \(b\) и нахождение остатка при делении на модуль \(n\). Он использует алгоритм бинарного возведения в степень (также называемый быстрым возведением в степень или методом возведения в квадрат), который сокращает количество операций с \(O(b)\) умножений до всего лишь \(O(\log b)\). Этот же алгоритм применяется в реальных криптографических реализациях, таких как RSA, Диффи-Хеллман и ElGamal.

Применение модульного возведения в степень

🔐

Шифрование RSA

Шифрование и дешифрование сообщений с использованием больших простых чисел

🤝

Диффи-Хеллман

Протокол обмена ключами для создания защищенных общих секретов

✍

Цифровые подписи

Алгоритмы DSA, ECDSA и EdDSA полагаются на модульное возведение в степень

🧪

Тестирование простоты

Тесты Ферма и Миллера-Рабина используют a^(n-1) mod n для проверки чисел

🏆

Олимпиадное программирование

Модульная арифметика с быстрым возведением в степень необходима во многих задачах

🔗

Блокчейн

Proof-of-work и криптографическое хеширование опираются на модульную арифметику

Как работает алгоритм бинарного возведения в степень

Основная идея заключается в том, что мы можем разложить любой показатель степени в сумму степеней двойки, используя его двоичное представление. Например, \(b = 13 = 1101_2 = 2^3 + 2^2 + 2^0\), следовательно, \(a^{13} = a^{8} \times a^{4} \times a^{1}\).

Алгоритм обрабатывает двоичные цифры показателя степени слева направо:

Шаг 1: Переведите показатель степени \(b\) в двоичную систему.

Шаг 2: Инициализируйте результат = 1 (или = основание, если первый бит равен 1).

Шаг 3: Для каждого последующего бита: Возведите в квадрат результат (mod n). Если бит равен 1, также умножьте на основание (mod n).

Шаг 4: После обработки всех битов результат будет равен \(a^b \bmod n\).

Псевдокод

function modpow(base, exp, mod):
    result = 1
    base = base mod mod
    while exp > 0:
        if exp is odd:        // бит равен 1
            result = (result × base) mod mod
        exp = exp >> 1        // сдвиг вправо (деление на 2)
        base = (base × base) mod mod
    return result

Основные формулы

Свойство	Формула	Описание
Модульное возведение в степень	\(a^b \bmod n\)	Остаток от деления a^b на n
Малая теорема Ферма	\(a^{p-1} \equiv 1 \pmod{p}\)	Для простого p и НОД(a,p)=1
Теорема Эйлера	\(a^{\phi(n)} \equiv 1 \pmod{n}\)	Для НОД(a,n)=1, где φ — функция Эйлера
Сложность бинарного метода	\(O(\log b)\) умножений	Не более 2·log₂(b) модульных умножений
Шифрование RSA	\(c = m^e \bmod n\)	Шифрование сообщения m открытым ключом (e, n)
Дешифрование RSA	\(m = c^d \bmod n\)	Дешифрование криптограммы c закрытым ключом d

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

Введите основание (a): Это число, которое вы хотите возвести в степень. Оно может быть положительным или отрицательным. Например, введите 7 для вычисления 7^256 mod 13.
Введите показатель степени (b): Это должно быть неотрицательное целое число. Оно представляет степень. Для криптографических приложений это число может быть очень большим (калькулятор поддерживает до 10^18).
Введите модуль (n): Это должно быть положительное целое число. Это число, на которое вы делите, чтобы получить остаток. В RSA это обычно произведение двух больших простых чисел.
Нажмите Рассчитать: Калькулятор вычислит a^b mod n с помощью бинарного возведения в степень и мгновенно покажет результат.
Смотрите анимацию: Нажмите «Старт», чтобы увидеть пошаговое выполнение алгоритма. Каждый бит показателя степени обрабатывается последовательно, показывая возведение в квадрат или возведение в квадрат с умножением.
Просмотрите отчет: Пошаговая таблица показывает каждое промежуточное вычисление, а сравнение эффективности демонстрирует, насколько бинарное возведение в степень быстрее обычного умножения.

Почему бинарное возведение в степень работает быстро

Рассмотрим вычисление \(2^{1000} \bmod 13\). Обычный подход требует 999 умножений. Бинарное возведение в степень преобразует 1000 в двоичное число (1111101000), которое состоит из 10 бит. Потребуется не более 9 возведений в квадрат плюс несколько умножений для каждого бита «1» — всего около 15 операций. Это примерно на 98.5% меньше операций. Для экспонент криптографического масштаба с сотнями цифр разница астрономическая: бинарный метод занимает тысячи операций, тогда как обычному методу потребовалось бы больше операций, чем атомов во вселенной.

FAQ

Что такое модульное возведение в степень?

Модульное возведение в степень вычисляет (a^b) mod n — возводит основание в степень, а затем берет остаток от деления на модуль. Это ключевая операция в криптографии с открытым ключом (RSA, Диффи-Хеллман, ElGamal), которая широко используется в теории чисел, олимпиадном программировании и информатике. Метод бинарного возведения в степень вычисляет это эффективно за O(log b) умножений.

Как работает бинарное возведение в степень (возведение в квадрат)?

Бинарное возведение в степень переводит показатель степени в двоичное представление, затем обрабатывает каждый бит слева направо (или справа налево). Для каждого бита текущий результат возводится в квадрат по модулю n. Если бит равен 1, результат дополнительно умножается на основание по модулю n. Это сокращает количество умножений с b−1 (простой метод) до максимум 2×log₂(b), что позволяет производить расчеты с огромными степенями.

Почему модульное возведение в степень важно в криптографии?

Шифрование RSA использует c = m^e mod n для зашифровки и m = c^d mod n для расшифровки, где n является произведением двух больших простых чисел, а показатели степени могут содержать сотни цифр. Без быстрого модульного возведения в степень эти операции были бы невыполнимы. Безопасность системы основана на том, что обратная операция (вычисление дискретного логарифма) считается вычислительно невозможной.

Может ли основание быть отрицательным?

Да, отрицательные основания полностью поддерживаются. Калькулятор сначала приводит основание по модулю n (используя арифметику Python, которая всегда возвращает неотрицательный результат для положительного n). Например, (−3)^2 mod 7 = 9 mod 7 = 2. Отрицательные результаты исключены, так как модульное приведение всегда дает значение в диапазоне [0, n−1].

Что происходит, когда модуль равен 1?

Любое целое число по модулю 1 равно 0. Это происходит потому, что при делении любого целого числа на 1 получается само число с остатком 0. Таким образом, a^b mod 1 = 0 для любых значений a и b. Калькулятор обрабатывает это как особый случай.

Ссылайтесь на этот контент, страницу или инструмент так:

"Калькулятор Модульного Возведения в Степень" на сайте https://ru.miniWebtool.com/калькулятор-модульного-возведения-в-степень/ от MiniWebtool, https://MiniWebtool.com/

от команды miniwebtool. Обновлено: 2026-04-16

Вы также можете попробовать наш AI Решатель Математических Задач GPT, чтобы решить ваши математические проблемы с помощью вопросов и ответов на естественном языке.