Алгоритм Фюрера (англ.
Fürer's algorithm) — быстрый
метод умножения больших целых чисел. Алгоритм был построен в 2007 году
швейцарским математиком Мартином Фюрером из университета штата
Пенсильвания как асимптотически более быстрый алгоритм, чем его
предшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971
году. Задача быстрого умножения больших чисел представляет большой
интерес в области криптографии с открытым ключом.
Предшественник алгоритма Фюрера, алгоритм Шёнхаге — Штрассена,
использовал быстрое преобразование Фурье для умножения больших чисел за
время
O(nlognloglogn), однако его авторы, и
Фолькер Штрассен, сделали предположение о существовании алгоритма,
способного решить проблему перемножения больших чисел за
O(nlogn). Алгоритм Фюрера заполнил промежуток между
этими границами: он может быть использован, чтобы перемножить числа за
время
O(nlogn⋅2O(log∗n)), где
log∗n —
итерированный логарифм числа
n. Однако разница по времени между
алгоритмами становится заметной при очень больших перемножаемых числах
(больше 10 000 000 000 000 значащих цифр).
В 2008 году Аниндая Де, Шэнден Саха, Пьюш Курур и Рампрасад Саптхариши
построили похожий алгоритм, основанный на модульной, а не комплексной
арифметике, достигнув при этом такого же времени работы.
Теория
Свёртка
Допустим, что мы перемножаем числа 123 и 456 «в столбик», однако без
выполнения переноса. Результат будет выглядеть так:
Если мы произведём перенос при обратном свёртывании, то результат будет
тот же, что и при произведении чисел по модулю
B
n + 1. В данном примере,
10
3 + 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 (это означает, что
a2n = 1 и
все меньшие степени
a не равны 1). Таким образом мы можем
определить третий вектор
A, называемый
вектор веса,
обладающий следующими свойствами:
Файл:DIT-FFT-butterfly.pngминиОперация
«бабочка».кольце; обычно оно берётся из поля комплексных чисел, но
фактически использовать комплексную арифметику с достаточной точностью,
чтобы обеспечить точные результаты, медленно и неэффективно. Вместо
этого мы можем использовать теоретико-числовое преобразование, которое
производит преобразование в поле целых чисел по модулю N для некоторого
целого N.
Так же как есть примитивные корни единицы любого порядка на комплексной
плоскости, при любом заданном
n мы можем выбрать подходящее N
такое, что
b — примитивный корень единицы порядка
n в
поле целых чисел по модулю N (другими словами,
bn ≡ 1 (mod N), и все меньшие степени
b не равны 1 mod N).
Алгоритм тратит большую часть времени на рекурсивное выполнение
произведения меньших чисел; в простом варианте алгоритма это происходит
в ряде мест:
-
Внутри алгоритма быстрого преобразования Фурье, примитивный корень
единицы b неоднократно возводится в степень и умножается на
другие числа.
-
При возведении в степень примитивного корня единицы a для
получения вектора веса A с последующим умножением векторов A или
A−1 на другие вектора.
-
При выполнении последовательного перемножения преобразованных
векторов.
Ключевой момент — выбрать N, модуль, равный
2
n + 1 для некоторого целого
n. У этого
способа есть ряд преимуществ в ряде стандартных систем, в которых
большие целые числа представлены в двоичном виде:
-
Любое число может быть быстро уменьшено по модулю
2n + 1 используя только сдвиг и сложение.
-
Любые примитивные корни единицы в этом кольце могут быть записаны в
форме 2k; соответственно мы можем умножать
или делить любое число на корень из единицы используя сдвиг.
-
Поэлементное рекурсивное перемножение преобразованный векторов может
быть выполнено, используя обратную свёртку, которая работает быстрее,
чем ациклическая свёртка, и в которой уже есть уменьшение результата
по модулю 2n + 1.
Отличие от
предшественника
Главное отличие от предшественника — многократное выполнение
компрессии числа, которое даёт вычислительную сложность
nlogn2O(log∗n) в отличие от однократного использования в
алгоритме Шёнхаге — Штрассена, которое даёт сложность
nlognloglogn Структура
алгоритма
Произведение целых чисел
Произведение целых чисел по модулю
Разложение
БПФ
Покомпонентное произведение
Обратное БПФ
Композиция результата