Алгоритмы быстрого возведения в степень по модулю
Алгоритмы быстрого возведения в степень по модулю — разновидность алгоритмов возведения в степень по модулю, широко использующихся в различных криптосистемах, для ускорения вычислительных операций с большими числами.
Метод с использованием Китайской теоремы об остатках
Описание метода
Пусть требуется вычислить , где числа достаточно большие и пусть модуль может быть разложен на простые делители . Тогда для быстрого возведения в степень по модулю можно воспользоваться китайской теоремой об остатках и решить систему уравнений (предварительно посчитав вычеты с использованием теоремы Ферма, где ):
Заменив на для удобства, решаем систему относительно и получаем .
Пусть требуется вычислить
Представим систему в виде
Подставив t из первого уравнения во второе, получим , тогда , или , или ;
подставив затем t из первого уравнения в третье с учетом выражения для получим или , тогда ;
тогда следовательно, ;
Применение
Значительный выигрыш от данного алгоритма можно получить при выполнении умножения. Умножение будет проводится в два раза быстрее при использовании данного алгоритма.
Вычислительная сложность
Данный метод позволяет сократить количество вычислений в раза. Пусть имеет длину бит. При обычном возведении в степень затратится около умножений по модулю. Пусть мы хотим вычислить . Сокращая на и задача сводится к вычислению . Каждая степень в данной записи имеет длину . Поэтому каждая операция возведения в степень потребует операций. Итого потребуется умножений по модулю простого числа или вместо изначального умножения по модулю .
Метод повторяющихся возведения в квадрат и умножения
Описание метода
Пусть требуется вычислить . Представим степень , где
Представим в виде:
Далее высчитывается значение выражения и проводится замена в преобразованном выражении.
Данная операция производится до тех пор пока не будет найден результат.
Пусть требуется вычислить . Представим степень в виде . Представим в виде
Применение
Если — простое или является произведением двух больших простых чисел, то обычно используют метод повторяющихся возведения в квадрат и умножения. Однако, если — составное, то обычно используют это метод вместе с китайской теоремой об остатках.
Вычислительная сложность
Средняя сложность данного алгоритма равна операций умножения двух -битовых чисел плюс операций деления -битовых чисел на -битовое число. Для -битовых и более длинных чисел данный алгоритм выполняется на ЭВМ достаточно быстро.
Метод Монтгомери возведения в степень
История
Данный метод был предложен 1985 году Питером Монтгомери для ускорения выполнения модульного возведения в степень.
Описание метода
В этом методе каждому числу ставится в соответствие некоторый образ и все вычисления производятся с , а в конце производится переход от образа к числу.
Теорема(Монтгомери). Пусть — взаимно простые положительные целые числа, а . Тогда для любого целого число делится на , причем . Более того, если , то разность равна либо , либо . |
Данная теорема позволяет вычислить оптимальным способом величину для некоторого удобно выбранного .
Определение 1. Для чисел , , , таких что НОД и , назовем — остатком числа величину . |
Определение 2. Произведением Монтгомери двух целых чисел , называется число |
Теорема (правила Монтгомери). Пусть числа , взаимно просты, и . Тогда и |
То есть, для наглядности, запишем выражение для возведения в степень:
Алгоритм(Произведение Монтгомери). Пусть заданы целые числа , где нечетно, а . Этот алгоритм возвращает .
|
Алгоритм(Метод Монтгомери возведения в степень). Пусть заданы числа , , и выбрано так же, как для алгоритма(Произведение Монтгомери). Этот алгоритм возвращает . Через мы обозначаем двоичные биты .
|
В итоге получаем образ , от которого мы можем получить конечный результат , причем выражение вычислено заранее. Для произведения двух чисел результат будет выглядеть как
Пусть , и хотим перемножить два числа и (т.е. возвести в квадрат)
имеет образ
(для проверки имеет образ )
Перемножаем образы:
,
Производим переход от образа умножения к искомому прообразу
,
,
Соответственно прообраз
Применение
Данный метод дает выигрыш в производительности по сравнению с методом повторяющихся возведения в квадрат и умножения, так как умножение двух чисел по модулю происходит значительно быстрее.
Вычислительная сложность
Данный метод позволяет уменьшить (при больших значения ) вычисления функции до одного умножения двух чисел размером . Сложность умножения Монтгомери оценивается как .
Алгоритм с использованием «школьного» метода
Описание метода
Для наглядности рассмотрим метод для основания , то есть будем проводить вычисления в — ичной (или двоичной, так как ) системе счисления. Основание имеет плюс, в том что выполнение операции деления на происходит сдвигом вправо, а умножение на — сдвигом влево.
Определение 1. Представлением неотрицательного целого числа в системе счисления с основанием (или -ичной записью числа ) называется кратчайшая последовательность целых чисел , называемых цифрами записи, такая что каждая из этих цифр удовлетворяет неравенству , и выполнено равенство |
Для примера, рассмотрим двоичный алгоритм взятия от произведения .
Алгоритм (двоичный алгоритм умножения и взятия остатка). Пусть заданы положительные целые числа , такие что ,. Этот алгоритм возвращает результат составной операции . Мы предполагаем, что задано двоичное представление числа согласно определению 1, так что биты числа имеют вид , и — самый старший бит.
|
Данный метод имеет один недостаток: он не использует преимущество многобитовой арифметики, доступной на любой современной ЭВМ. Поэтому обычно используют основания большие .
Вычислительная сложность «школьного» метода
Выражения вида имеет оценку вычислительной сложности —
См. также
Примечания
Литература
- Крэндалл Ричард, Померанс Карл. Простые числа: Криптографические и вычислительные аспекты / Под ред. и с предисл. В. Н. Чубарикова.. — М.: УРСС:: Книжный Дом «ЛИБРОКОМ», 2011. — 664 с. — ISBN 978-5-453-00016-6, 978-5-397-03060-2.
- Молдовян Н. А. Теоретический минимум и алгоритмы цифровой подписи. — СПб.: БВХ-Петербург: Книжный Дом «ЛИБРОКОМ», 2010. — 304 с. — ISBN 978-5-9775-0585-7.
- Фергюнсон, Нильс, Шнайер, Брюс. Практическая криптография. — M.: Издательский дом «Вильямс», 2004. — 432 с. — ISBN 5-8459-0733-0.
- Мао В. Современная криптография: Теория и практика / пер. Д. А. Клюшина — М.: Вильямс, 2005. — 768 с. — ISBN 978-5-8459-0847-6