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

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

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

Описание метода править

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

 

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

Применение править

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

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

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

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

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

Описание метода править

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

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

 

 

 

 

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

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

Применение править

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

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

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

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

История править

Данный метод был предложен 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