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

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

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

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

Теория править

Свёртка править

Допустим, что мы перемножаем числа 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 — примитивный корень порядка 2n (это означает, что a²ⁿ = 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).

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

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

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

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

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

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

Структура алгоритма править

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

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

Разложение

БПФ

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

Обратное БПФ

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

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

↑ ¹ ² Fürer, M. (2007). «Faster Integer Multiplication Архивировано 25 апреля 2013 года.» in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
↑ A. Schönhage and V. Strassen, «Schnelle Multiplikation großer Zahlen», Computing 7 (1971), pp. 281—292.
↑ Alexander J. Yee. Алгоритмы в y-cruncher — самой быстрой программе для вычисления различных констант с высокой точностью. (англ.) (21 июня 2014). Дата обращения: 24 июня 2014. Архивировано 30 марта 2014 года.
↑ Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication Using Modular Arithmetic. Symposium on Theory of Computation (STOC) 2008. arXiv:0801.1416

[fürer_1-1] ¹ ² Fürer, M. (2007). «Faster Integer Multiplication Архивировано 25 апреля 2013 года.» in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA

[2] A. Schönhage and V. Strassen, «Schnelle Multiplikation großer Zahlen», Computing 7 (1971), pp. 281—292.

[3] Alexander J. Yee. Алгоритмы в y-cruncher — самой быстрой программе для вычисления различных констант с высокой точностью. (англ.) (21 июня 2014). Дата обращения: 24 июня 2014. Архивировано 30 марта 2014 года.

[4] Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Fast Integer Multiplication Using Modular Arithmetic. Symposium on Theory of Computation (STOC) 2008. arXiv:0801.1416

[1]

[2]

[3]

[4]