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

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

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

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

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