Алгоритмы быстрого возведения в степень по модулю — разновидность алгоритмов возведения в степень по модулю, широко использующихся в различных криптосистемах, для ускорения вычислительных операций с большими числами.
Метод с использованием Китайской теоремы об остатках
Описание метода
Пусть требуется вычислить , где числа достаточно большие и пусть модуль может быть разложен на простые делители . Тогда для быстрого возведения в степень по модулю можно воспользоваться китайской теоремой об остатках и решить систему уравнений (предварительно посчитав вычеты с использованием теоремы Ферма, где ):
Заменив на для удобства, решаем систему относительно и получаем .
Применение
Значительный выигрыш от данного алгоритма можно получить при выполнении умножения. Умножение будет проводиться в два раза быстрее при использовании данного алгоритма.
Вычислительная сложность
Данный метод позволяет сократить количество вычислений в раза. Пусть имеет длину бит. При обычном возведении в степень затратится около умножений по модулю. Пусть мы хотим вычислить . Сокращая на и задача сводится к вычислению . Каждая степень в данной записи имеет длину . Поэтому каждая операция возведения в степень потребует операций. Итого потребуется умножений по модулю простого числа или вместо изначального умножения по модулю .
Метод повторяющихся возведения в квадрат и умножения
Описание метода
Пусть требуется вычислить . Представим степень , где
Представим в виде:
Далее высчитывается значение выражения , и проводится замена в преобразованном выражении.
Данная операция производится до тех пор, пока не будет найден результат.
Применение
Если — простое или является произведением двух больших простых чисел, то обычно используют метод повторяющихся возведения в квадрат и умножения. Однако, если — составное, то обычно используют это метод вместе с китайской теоремой об остатках.
Вычислительная сложность
Средняя сложность данного алгоритма равна операций умножения двух -битовых чисел плюс операций деления -битовых чисел на -битовое число. Для -битовых и более длинных чисел данный алгоритм выполняется на ЭВМ достаточно быстро.
Метод Монтгомери возведения в степень
История
Данный метод был предложен 1985 году Питером Монтгомери для ускорения выполнения модульного возведения в степень.
Описание метода
В этом методе каждому числу ставится в соответствие некоторый образ и все вычисления производятся с , а в конце производится переход от образа к числу.
Теорема(Монтгомери).
Пусть — взаимно простые положительные целые числа, а . Тогда для любого целого число делится на , причем . Более того, если , то разность равна либо , либо .
Данная теорема позволяет вычислить оптимальным способом величину для некоторого удобно выбранного .
Определение 1. Для чисел , , , таких что НОД и , назовем — остатком числа величину .
Определение 2. Произведением Монтгомери двух целых чисел , называется число
Теорема (правила Монтгомери). Пусть числа , взаимно просты, и . Тогда и
То есть, для наглядности, запишем выражение для возведения в степень:
Алгоритм(Произведение Монтгомери). Пусть заданы целые числа , где нечетно, а . Этот алгоритм возвращает .
1.[Функция M Монтгомери]
//В соответствии с теоремой(Монтгомери). 2.[Поправить результат] if ; return ;
Алгоритм(Метод Монтгомери возведения в степень). Пусть заданы числа , , и выбрано так же, как для алгоритма(Произведение Монтгомери). Этот алгоритм возвращает . Через мы обозначаем двоичные биты .
1.[Начальная установка] ; //С помощью какого-либо метода деления с остатком. ; //С помощью какого-либо метода деления с остатком. 2.[Схема возведения в степень] for { ; //с помощью алгоритма(произведение Монтгомери). if ; } //Теперь равняется . 3.[Окончательное получение степени]
В итоге получаем образ , от которого мы можем получить конечный результат , причем выражение вычислено заранее. Для произведения двух чисел результат будет выглядеть как
Применение
Данный метод дает выигрыш в производительности по сравнению с методом повторяющихся возведения в квадрат и умножения, так как умножение двух чисел по модулю происходит значительно быстрее.
Вычислительная сложность
Данный метод позволяет уменьшить (при больших значения ) вычисления функции до одного умножения двух чисел размером . Сложность умножения Монтгомери оценивается как .
Алгоритм с использованием «школьного» метода
Описание метода
Для наглядности рассмотрим метод для основания , то есть будем проводить вычисления в — ичной (или двоичной, так как ) системе счисления. Основание имеет плюс, в том что выполнение операции деления на происходит сдвигом вправо, а умножение на — сдвигом влево.
Определение 1. Представлением неотрицательного целого числа в системе счисления с основанием (или -ичной записью числа ) называется кратчайшая последовательность целых чисел , называемых цифрами записи, такая что каждая из этих цифр удовлетворяет неравенству , и выполнено равенство
Для примера, рассмотрим двоичный алгоритм взятия от произведения .
Алгоритм (двоичный алгоритм умножения и взятия остатка). Пусть заданы положительные целые числа , такие что ,. Этот алгоритм возвращает результат составной операции . Мы предполагаем, что задано двоичное представление числа согласно определению 1, так что биты числа имеют вид , и — самый старший бит.
1.[Начальная установка] ; 2.[Преобразовать все битов] for { ; if ; if ; if ; } return ;
Данный метод имеет один недостаток: он не использует преимущество многобитовой арифметики, доступной на любой современной ЭВМ. Поэтому обычно используют основания большие .
Вычислительная сложность «школьного» метода
Выражения вида имеет оценку вычислительной сложности —
См. также Возведение в степень по модулю Алгоритмы быстрого возведения в степень
Примечания
Литература
Категория:Теоретико-числовые алгоритмы