Алгоритм Фюрера ( англ. Fürer’s algorithm ) — быстрый больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его предшественник, алгоритм Шёнхаге — Штрассена , опубликованный в 1971 году . Задача быстрого умножения больших чисел представляет большой интерес в области криптографии с открытым ключом .

Предшественник алгоритма Фюрера, алгоритм Шёнхаге — Штрассена, использовал быстрое преобразование Фурье для умножения больших чисел за время ${\displaystyle O\left(n\log n\log \log n\right)}$ , однако его авторы, ( нем. ) и Фолькер Штрассен , сделали предположение о существовании алгоритма, способного решить проблему перемножения больших чисел за ${\displaystyle O\left(n\log n\right)}$ . Алгоритм Фюрера заполнил промежуток между этими границами: он может быть использован, чтобы перемножить числа за время ${\displaystyle O(n\log n\cdot 2^{O(\log ^{*}n)})}$ , где ${\displaystyle \log ^{*}n}$ — итерированный логарифм числа n . Однако разница по времени между алгоритмами становится заметной при очень больших перемножаемых числах (больше 10 000 000 000 000 значащих цифр).

В 2008 году Аниндая Де, Шэнден Саха, Пьюш Курур и Рампрасад Саптхариши построили похожий алгоритм, основанный на модульной , а не комплексной арифметике, достигнув при этом такого же времени работы .

Теория

Свёртка

Допустим, что мы перемножаем числа 123 и 456 «в столбик», однако без выполнения переноса. Результат будет выглядеть так:

		1	2	3
	×	4	5	6
		6	12	18
	5	10	15
4	8	12
4	13	28	27	18

Эта последовательность (4, 13, 28, 27, 18) называется ациклической или линейной свёрткой от последовательностей (1,2,3) и (4,5,6). Зная ациклическую свёртку двух последовательностей, рассчитать произведение несложно: достаточно выполнить перенос (например, в самом правом столбце, мы оставляем 8 и добавляем 1 к столбцу, содержащему 27). В нашем примере это приводит к результату 56088.

Есть и другие типы свёрток, которые могут быть полезны. Допустим, что входящие последовательности содержат n элементов (в примере — 3). Тогда результирующая линейная свёртка содержит n + n − 1 элементов; если мы возьмём самый правый столбец n элементов и добавим самый левый столбец n − 1 ', в результате мы получим циклическую свёртку:

	28	27	18
+		4	13
	28	31	31

Если мы произведём перенос при циклическом свёртывании, результат будет тот же, что и при произведении чисел по модулю B ⁿ − 1 (в данном примере это 10 ³ − 1 = 999). Выполним перенос (пока не циклический): (31+3=34, 28+3=31) и получим 3141. Если прибавить к правой единице левую тройку, получим 144 ≡ 56088 (mod 999) (Перенос должен выполняться циклически, то есть 3 из младшей 31 добавится к старшей 31, 3 из полученных 34 добавится к 28 и тройка из полученных 31 добавится к младшему разряду, то есть к 1).

Наоборот, если мы возьмём самый правый столбец n элементов и вычтем самый левый столбец n −1 элементов, то в результате мы получим обратную свёртку:

	28	27	18
−		4	13
	28	23	5

Если мы произведём перенос при обратном свёртывании, то результат будет тот же, что и при произведении чисел по модулю B ⁿ + 1. В данном примере, 10 ³ + 1 = 1001, выполним перенос по (28, 23, 5) и получим 3035, при этом 3035 ≡ 56088 (mod 1001). Обратная свёртка может содержать отрицательные числа, которые могут быть убраны во время переноса, используя ту же технику, что и при длинных вычитаниях.

Теорема о свёртке

Как и другие методы, основанные на быстром преобразовании Фурье, алгоритм Фюрера в корне зависит от теоремы о свёртке, которая обеспечивает эффективный способ посчитать циклическую свёртку двух последовательностей. Её идея состоит в следующем:

Циклическая свёртка двух векторов может быть найдена через дискретное преобразование Фурье (ДПФ) каждого из них, путём произведения результирующих векторов элемент за элементом, с последующим обратным преобразованием Фурье (ОДПФ).

Или через формулы:

CyclicConvolution(X, Y) = IDFT(DFT(X) · DFT(Y)), где:

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

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

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

Если мы посчитаем ДПФ и ОДПФ, используя быстрое преобразование Фурье, и вызовем наш алгоритм перемножения рекурсивно, чтобы перемножить входы(?) преобразованных векторов DFT(X) и DFT(Y), то в результате мы получим эффективный алгоритм для расчёта циклической свёртки.

В этом алгоритме гораздо эффективней считать обратную циклическую свёртку; как оказывается, немного модифицированная версия теоремы о свёртке может позволить и это. Предположим, что вектора X и Y имеют длину n , и a — примитивный корень порядка 2 n (это означает, что a ^{2 n} = 1 и все меньшие степени a не равны 1). Таким образом, мы можем определить третий вектор A , называемый вектор веса , обладающий следующими свойствами:

A = ( a ^j ), 0 ≤ j < n

A ⁻¹ = ( a ^−j ), 0 ≤ j < n

Теперь мы можем записать:

NegacyclicConvolution( X , Y ) = A ⁻¹ · IDFT(DFT( A · X ) · DFT( A · Y )), где

NegacyclicConvolution — Обратная циклическая свёртка ,

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

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

Другими словами, это то же самое за исключением того, что входящие векторы умножены на A , а результат умножен на A ⁻¹ .

Выбор кольца

Дискретное преобразование Фурье — абстрактная операция, которая может быть выполнена в любом алгебраическом кольце ; обычно оно берётся из поля комплексных чисел, но фактически использовать комплексную арифметику с достаточной точностью, чтобы обеспечить точные результаты, медленно и неэффективно. Вместо этого мы можем использовать теоретико-числовое преобразование, которое производит преобразование в поле целых чисел по модулю N для некоторого целого N.

Так же как есть примитивные корни единицы любого порядка на комплексной плоскости, при любом заданном n мы можем выбрать подходящее N такое, что b — примитивный корень единицы порядка n в поле целых чисел по модулю N (другими словами, b ⁿ ≡ 1 (mod N), и все меньшие степени b не равны 1 mod N).

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

1. Внутри алгоритма быстрого преобразования Фурье, примитивный корень единицы b неоднократно возводится в степень и умножается на другие числа.
2. При возведении в степень примитивного корня единицы a для получения вектора веса A с последующим умножением векторов A или A ⁻¹ на другие вектора.
3. При выполнении последовательного перемножения преобразованных векторов.

Ключевой момент — выбрать N, модуль, равный 2 ⁿ + 1 для некоторого целого n . У этого способа есть ряд преимуществ в ряде стандартных систем, в которых большие целые числа представлены в двоичном виде:

• Любое число может быть быстро уменьшено по модулю 2 ⁿ + 1 используя только сдвиг и сложение.
• Любые примитивные корни единицы в этом кольце могут быть записаны в форме 2 ^k ; соответственно мы можем умножать или делить любое число на корень из единицы используя сдвиг.
• Поэлементное рекурсивное перемножение преобразованных векторов может быть выполнено, используя обратную свёртку, которая работает быстрее, чем ациклическая свёртка, и в которой уже есть уменьшение результата по модулю 2 ⁿ + 1.

Отличие от предшественника

Главное отличие от предшественника — многократное выполнение компрессии числа, которое даёт вычислительную сложность ${\displaystyle n\log n\,2^{O(\log ^{*}n)}}$ в отличие от однократного использования в алгоритме Шёнхаге — Штрассена, которое даёт сложность ${\displaystyle n\log n\log \log n}$

Структура алгоритма

Произведение целых чисел

Произведение целых чисел по модулю

Разложение

БПФ

Покомпонентное произведение

Обратное БПФ

Композиция результата

Примечания