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

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

Калькулятор модульного возведения в степень вычисляет \(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

Продвинутые математические операции:

• Калькулятор матрицы смежности Новый
• Антилогарифмический Калькулятор
• Калькулятор бета-функции
• Калькулятор биномиального коэффициента
• Калькулятор биномиального распределения
• Побитовый калькулятор Популярное
• Упроститель Булевой Алгебры Новый
• Калькулятор центральной предельной теоремы
• Калькулятор китайской теоремы об остатках
• Комбинированный калькулятор
• Калькулятор дополнительной функции ошибки
• Калькулятор комплексных чисел Популярное
• Калькулятор цепных дробей
• Калькулятор беспорядков (субфакториал)
• Калькулятор кратчайшего пути Дейкстры
• Калькулятор Энтропии
• Калькулятор функции ошибки
• Калькулятор функции Эйлера
• Калькулятор экспоненциального распада
• Калькулятор экспоненциального роста: высокая точность
• Калькулятор экспоненциального интеграла
• Калькулятор показателей (высокая точность)
• Калькулятор расширенного алгоритма Евклида
• Калькулятор факториала Популярное
• Калькулятор гамма-функции
• Калькулятор золотого сечения
• Калькулятор раскраски графов Новый
• Валидатор последовательности степеней графа
• Калькулятор Порядка в Теории Групп Новый
• Калькулятор полураспада
• Проверка Гамильтонова Пути Новый
• Калькулятор формулы включений-исключений Новый
• Решатель Карты Карно (K-Map) Популярное
• Решатель Линейного Программирования Новый
• Калькулятор стационарного распределения цепи Маркова
• Калькулятор минимального остовного дерева
• Калькулятор Модульного Возведения в Степень Новый
• Калькулятор модулярного мультипликативного обратного
• Калькулятор отрицательного биномиального распределения Новый
• Калькулятор сетевого потока (Максимальный поток) Новый
• Калькулятор процентного роста
• Калькулятор перестановок
• Калькулятор перестановок с повторениями Новый
• Калькулятор принципа голубятни
• Проверка планарного графа Новый
• Калькулятор распределения Пуассона
• Калькулятор корней многочленов с подробными шагами
• Калькулятор первообразного корня
• Калькулятор вероятности
• Калькулятор распределения вероятностей
• Калькулятор пропорций
• Калькулятор квадратичных формул
• Калькулятор Колец и Полей Новый
• Калькулятор округления Новый
• Научный Калькулятор
• Калькулятор экспоненциальной записи
• Калькулятор теории множеств Популярное
• Калькулятор значащих цифр Новый
• Решатель задачи о стабильных браках Новый
• Калькулятор чисел Стирлинга
• Калькулятор суммы кубов
• Калькулятор суммы последовательных чисел
• Калькулятор суммы квадратов
• Калькулятор топологической сортировки Новый
• Решатель задачи коммивояжёра (TSP) Новый
• Генератор таблицы истинности
• Генератор диаграммы Венна (3 множества)