АЛГОРИТМЫ БЫСТРОГО УМНОЖЕНИЯ

Введение

Быстрые алгоритмы — это область вычислительной математики, которая изучает алгоритмы вычисления заданной функции с заданной точностью с использованием как можно меньшего числа битовых операций. Быстрые алгоритмы, реализованные на ЭВМ в программном или аппаратном обеспечении, значительно увеличивают производительность вычислений, а иногда и решают задачи, размер которых не позволял найти решение путём применения обычных методов вычисления.

Быстрые алгоритмы имеют большое значение в современной криптографии с открытым ключом.

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

Алгоритм Карацубы

Алгоритм был открыт в 1960 году и является первым методом быстрого умножения.  Он открыл новое направление в вычислительной математике — теорию создания быстрых алгоритмов. Сложность алгоритма 2^log₂³

Пусть числа a и b натуральные длины n=2k разрядов в системе счисления с основанием B. Представим a и b  в системе счисления с основанием B^k :

a=(a₁a₀)_Bk, b=(b₁,b₀)_Bk.

Если умножить a на b традиционным способом то:

ab = B^2ka₁b₁+B^k(a₀b₁+a₁b₀)+a₀b₀ ,

требуется четыре умножения по основанию B^k и n²=4k² элементарных умножений по основанию B. Однако, если представить

c₀ := a₀b₀,

с₁ := a₁b₁,

с₂ :=(a₀+a₁)(b₀+b₁)-c₀-c₁, то

ab := B^k(B^kc₁+c₂)+c₀.

Следовательно, при таком представлении произведения ab, необходимо всего три умножения по основанию B^k, или, то же самое, 3k² умножений по основанию B.

Метод умножения Шёнхаге – Штрассена

Данные метод был опубликован в 1971 году. Основной идей метода является быстрое преобразование Фурье. До 2007 года данный метод считался асимптотический быстрейшим из всех известных на тот момент для целых чисел, порядок которых больше чем 10¹⁰⁰⁰⁰.

Сложность метода O(log(N*log(N)*loglog(N))).

Формулировка требований

Пусть заданы два неотрицательных числа x, y, имеющих не больше D цифр в некоторой системе счисления с основанием B. Этот алгоритм возвращает представление произведения xy в системе счисления с основанием B.

Алгоритм

1. [Начальные требования]

Дополнить нулями x, y до тех пор, пока каждое из них не станет числом     размера 2D, так что циклическая свертка новых последовательностей будет содержать ациклическую свертку исходных последовательностей:

2. [Преобразование Фурье]

X=(x)

Y=(x)

3. [Покомпонентные умножения]

Z=X*Y

4. [Обратное преобразование]

z = (Z)

5. [Округление цифр результата]

z = round (z)

6. [Выполнение переносов по основанию B]

carry =0

for (-1<n<2D) {

v=zn + carry;

zn = v mod B;

carry = [v/B];

}

7. [Учет последней цифры]

Удалить начальные нули, возможно, carry >0 станет старшей цифры числа z;

return z;

Алгоритм Фюрера

Алгоритм был построен швейцарским математиком Мартином Фюрером в 2007 году. Он является асимптотически более быстрым, чем алгоритм Шенхаге-Штрассена. Разница по времени исполнения видна для чисел, имеющих больше 10 000 000 000 000 значащих цифру. Сложность алгоритма Фюрера O(nlog(n)*2^O(log*n)), где log*(n) итерированный логарифм n.

Алгоритм основан на БПФ и зависит от теоремы о свертке. Теорема о свертке предоставляет эффективный способ вычислить циклическую свертку двух последовательностей.

Формула циклической свертки:

ЦС(X, Y) =ОДПФ(ДПФ(X)*ДПФ(Y)), где

ЦЦ — циклическая свёртка,

ДПФ — дискретное преобразование Фурье,

ОДПФ— обратное дискретное преобразование Фурье.

Рисунок 1. Операция «Бабочка»

Выбор кольца

ДПФ может быть выполнено практически в любом кольце.

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

Важным моментом является выбор модуля N= 2ⁿ+1.

Список литературы:

1. Вельшенбах, М. Криптография на Си и С++ в действии. Учебное пособие - М.: Триумф, 2014. - 462 c.
2. Крэндалл Р., Померанс К. Простые числа: криптографические и вычислительные аспекты. М.: УРСС: Либроком, 2011. 664 с.