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

Алгоритм Фюрера (англ. Fürer's algorithm) — быстрыйметод умножения больших целых чисел. Алгоритм был построен в 2007 годушвейцарским математиком Мартином Фюрером из университета штатаПенсильвания как асимптотически более быстрый алгоритм, чем егопредшественник, алгоритм Шёнхаге — Штрассена, опубликованный в 1971году. Задача быстрого умножения больших чисел представляет большойинтерес в области криптографии с открытым ключом.
 Предшественник алгоритма Фюрера, алгоритм Шёнхаге — Штрассена,использовал быстрое преобразование Фурье для умножения больших чисел завремя O(nlognloglogn), однако его авторы, иФолькер Штрассен, сделали предположение о существовании алгоритма,способного решить проблему перемножения больших чисел заO(nlogn). Алгоритм Фюрера заполнил промежуток междуэтими границами: он может быть использован, чтобы перемножить числа завремя O(nlogn2O(logn)), где logn —итерированный логарифм числа n. Однако разница по времени междуалгоритмами становится заметной при очень больших перемножаемых числах(больше 10 000 000 000 000 значащих цифр).
 В 2008 году Аниндая Де, Шэнден Саха, Пьюш Курур и Рампрасад Саптхаришипостроили похожий алгоритм, основанный на модульной, а не комплекснойарифметике, достигнув при этом такого же времени работы.

Теория


Свёртка


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

 Если мы произведём перенос при обратном свёртывании, то результат будеттот же, что и при произведении чисел по модулюBn + 1. В данном примере,103 + 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 (это означает, что a2n = 1 ивсе меньшие степени a не равны 1). Таким образом мы можемопределить третий вектор A, называемый вектор веса,обладающий следующими свойствами:Файл:DIT-FFT-butterfly.pngминиОперация«бабочка».кольце; обычно оно берётся из поля комплексных чисел, нофактически использовать комплексную арифметику с достаточной точностью,чтобы обеспечить точные результаты, медленно и неэффективно. Вместоэтого мы можем использовать теоретико-числовое преобразование, котороепроизводит преобразование в поле целых чисел по модулю N для некоторогоцелого N.
 Так же как есть примитивные корни единицы любого порядка на комплекснойплоскости, при любом заданном n мы можем выбрать подходящее Nтакое, что b — примитивный корень единицы порядка n вполе целых чисел по модулю N (другими словами,bn ≡ 1 (mod N), и все меньшие степениb не равны 1 mod N).
 Алгоритм тратит большую часть времени на рекурсивное выполнениепроизведения меньших чисел; в простом варианте алгоритма это происходитв ряде мест:

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

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

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

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


 Главное отличие от предшественника — многократное выполнениекомпрессии числа, которое даёт вычислительную сложностьnlogn2O(logn) в отличие от однократного использования валгоритме Шёнхаге — Штрассена, которое даёт сложностьnlognloglogn

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


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

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

 Разложение
 БПФ
 Покомпонентное произведение
 Обратное БПФ
 Композиция результата