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