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

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

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

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

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

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

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

Псевдокод

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

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

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

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

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

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

FAQ