Interested Article - Алгоритмы быстрого возведения в степень по модулю

Алгоритмы быстрого возведения в степень по модулю — разновидность алгоритмов возведения в степень по модулю , широко использующихся в различных криптосистемах, для ускорения вычислительных операций с большими числами.

Метод с использованием Китайской теоремы об остатках

Описание метода

Пусть требуется вычислить , где числа достаточно большие и пусть модуль может быть разложен на простые делители . Тогда для быстрого возведения в степень по модулю можно воспользоваться китайской теоремой об остатках и решить систему уравнений (предварительно посчитав вычеты с использованием теоремы Ферма, где ):

Заменив на для удобства, решаем систему относительно и получаем .

Применение

Значительный выигрыш от данного алгоритма можно получить при выполнении умножения. Умножение будет проводится в два раза быстрее при использовании данного алгоритма.

Вычислительная сложность

Данный метод позволяет сократить количество вычислений в раза. Пусть имеет длину бит. При обычном возведении в степень затратится около умножений по модулю. Пусть мы хотим вычислить . Сокращая на и задача сводится к вычислению . Каждая степень в данной записи имеет длину . Поэтому каждая операция возведения в степень потребует операций. Итого потребуется умножений по модулю простого числа или вместо изначального умножения по модулю .

Метод повторяющихся возведения в квадрат и умножения

Пример блок-схемы метода повторяющихся возведения в квадрат и умножения

Описание метода

Пусть требуется вычислить . Представим степень , где

Представим в виде:

Далее высчитывается значение выражения и проводится замена в преобразованном выражении.

Данная операция производится до тех пор пока не будет найден результат.

Применение

Если — простое или является произведением двух больших простых чисел, то обычно используют метод повторяющихся возведения в квадрат и умножения. Однако, если — составное, то обычно используют это метод вместе с китайской теоремой об остатках.

Вычислительная сложность

Средняя сложность данного алгоритма равна операций умножения двух -битовых чисел плюс операций деления -битовых чисел на -битовое число. Для -битовых и более длинных чисел данный алгоритм выполняется на ЭВМ достаточно быстро.

Метод Монтгомери возведения в степень

История

Данный метод был предложен 1985 году Питером Монтгомери для ускорения выполнения модульного возведения в степень.

Описание метода

В этом методе каждому числу ставится в соответствие некоторый образ и все вычисления производятся с , а в конце производится переход от образа к числу.

Теорема(Монтгомери).

Пусть — взаимно простые положительные целые числа, а . Тогда для любого целого число делится на , причем . Более того, если , то разность равна либо , либо .

Данная теорема позволяет вычислить оптимальным способом величину для некоторого удобно выбранного .

Определение 1. Для чисел , , , таких что НОД и , назовем — остатком числа величину .

Определение 2. Произведением Монтгомери двух целых чисел , называется число

Теорема (правила Монтгомери). Пусть числа , взаимно просты, и . Тогда и

То есть, для наглядности, запишем выражение для возведения в степень:

Алгоритм(Произведение Монтгомери). Пусть заданы целые числа , где нечетно, а . Этот алгоритм возвращает .

1.[Функция M Монтгомери]
{
;
;
//В соответствии с теоремой(Монтгомери) .
2.[Поправить результат]
if ;
return ;
}

Алгоритм(Метод Монтгомери возведения в степень). Пусть заданы числа , , и выбрано так же, как для алгоритма(Произведение Монтгомери). Этот алгоритм возвращает . Через мы обозначаем двоичные биты .

1.[Начальная установка]
;
//С помощью какого-либо метода деления с остатком.
;
//С помощью какого-либо метода деления с остатком.
2.[Схема возведения в степень]
for {
;
//с помощью алгоритма(произведение Монтгомери) .
if ;
}
//Теперь равняется .
3.[Окончательное получение степени]
;

В итоге получаем образ , от которого мы можем получить конечный результат , причем выражение вычислено заранее. Для произведения двух чисел результат будет выглядеть как

Применение

Данный метод дает выигрыш в производительности по сравнению с методом повторяющихся возведения в квадрат и умножения, так как умножение двух чисел по модулю происходит значительно быстрее.

Вычислительная сложность

Данный метод позволяет уменьшить (при больших значения ) вычисления функции до одного умножения двух чисел размером . Сложность умножения Монтгомери оценивается как .

Алгоритм с использованием «школьного» метода

Описание метода

Для наглядности рассмотрим метод для основания , то есть будем проводить вычисления в — ичной (или двоичной, так как ) системе счисления. Основание имеет плюс, в том что выполнение операции деления на происходит сдвигом вправо, а умножение на — сдвигом влево.

Определение 1. Представлением неотрицательного целого числа в системе счисления с основанием (или -ичной записью числа ) называется кратчайшая последовательность целых чисел , называемых цифрами записи, такая что каждая из этих цифр удовлетворяет неравенству , и выполнено равенство

Для примера, рассмотрим двоичный алгоритм взятия от произведения .

Алгоритм (двоичный алгоритм умножения и взятия остатка). Пусть заданы положительные целые числа , такие что , . Этот алгоритм возвращает результат составной операции . Мы предполагаем, что задано двоичное представление числа согласно определению 1 , так что биты числа имеют вид , и — самый старший бит.

1.[Начальная установка]
;
2.[Преобразовать все битов]
for {
;
if ;
if ;
if ;
}
return ;

Данный метод имеет один недостаток: он не использует преимущество многобитовой арифметики, доступной на любой современной ЭВМ. Поэтому обычно используют основания большие .

Вычислительная сложность «школьного» метода

Выражения вида имеет оценку вычислительной сложности —

См. также

Примечания

Литература

  • Крэндалл Ричард, Померанс Карл. Простые числа: Криптографические и вычислительные аспекты / Под ред. и с предисл. В. Н. Чубарикова.. — М.: УРСС:: Книжный Дом «ЛИБРОКОМ», 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
Источник —

Same as Алгоритмы быстрого возведения в степень по модулю