Алгоритм Шенхаге – Штрассена

Алгоритм умножения

Алгоритм Шёнхаге–Штрассена основан на методе быстрого преобразования Фурье (БПФ) целочисленного умножения . Этот рисунок демонстрирует умножение 1234 × 5678 = 7006652 с использованием простого метода БПФ. Основание 10 используется вместо основания 2 ^w для иллюстративных целей.

Шёнхаге (справа) и Штрассен (слева) играют в шахматы в Обервольфахе , 1979 г.

Алгоритм Шёнхаге–Штрассена — асимптотически быстрый алгоритм умножения больших целых чисел , опубликованный Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году. ^[1] Он работает путем рекурсивного применения быстрого преобразования Фурье (БПФ) к целым числам по модулю . Сложность выполнения битов для умножения двух n -значных чисел с использованием алгоритма находится в нотации O большое . ${\displaystyle 2^{n}+1}$ ${\displaystyle O(n\cdot \log n\cdot \log \log n)}$

Алгоритм Шёнхаге–Штрассена был асимптотически самым быстрым методом умножения, известным с 1971 по 2007 год. Он асимптотически быстрее старых методов, таких как умножение Карацубы и Тоома–Кука , и начинает превосходить их на практике для чисел свыше 10 000–100 000 десятичных знаков. ^[2] В 2007 году Мартин Фюрер опубликовал алгоритм с более быстрой асимптотической сложностью. ^[3] В 2019 году Дэвид Харви и Йорис ван дер Хувен продемонстрировали, что многозначное умножение имеет теоретическую сложность; однако их алгоритм имеет постоянные множители, которые делают его невыносимо медленным для любой мыслимой практической задачи (см. галактический алгоритм ). ^[4] ${\displaystyle O(n\log n)}$

Приложения алгоритма Шёнхаге–Штрассена включают большие вычисления, выполняемые ради них самих, такие как Великий интернет-поиск простых чисел Мерсенна и приближения числа π , а также практические приложения, такие как факторизация эллиптической кривой Ленстры с помощью подстановки Кронекера , которая сводит умножение полиномов к умножению целых чисел. ^{[5] [6]}

Описание

В этом разделе представлена ​​упрощенная версия алгоритма, показывающая, как вычислить произведение двух натуральных чисел по модулю числа вида , где — некоторое фиксированное число. Целые числа должны быть разделены на блоки бит, поэтому в практических реализациях важно найти правильный баланс между параметрами . В любом случае этот алгоритм предоставит способ умножения двух положительных целых чисел, при условии, что выбрано так, что . ${\displaystyle ab}$ ${\displaystyle a,b}$ ${\displaystyle 2^{n}+1}$ ${\displaystyle n=2^{k}M}$ ${\displaystyle a,b}$ ${\displaystyle D=2^{k}}$ ${\displaystyle M}$ ${\displaystyle M,k}$ ${\displaystyle n}$ ${\displaystyle ab<2^{n}+1}$

Пусть будет числом бит в сигналах и , где — степень двойки. Разделим сигналы и на блоки бит каждый, сохранив полученные блоки в виде массивов (элементы которых мы будем рассматривать для простоты как целые числа произвольной точности). ${\displaystyle n=DM}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle D=2^{k}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle A,B}$

Теперь выберем модуль для преобразования Фурье следующим образом. Пусть будет таким, что . Также положим , и рассмотрим элементы массивов как (произвольной точности) целые числа по модулю . Заметим, что поскольку , модуль достаточно велик, чтобы вместить любые переносы, которые могут возникнуть в результате умножения и . Таким образом, произведение (по модулю ) можно вычислить, оценив свертку . Кроме того, при , мы имеем , и поэтому является примитивным корнем th из единицы по модулю . ${\displaystyle M'}$ ${\displaystyle DM'\geq 2M+k}$ ${\displaystyle n'=DM'}$ ${\displaystyle A,B}$ ${\displaystyle 2^{n'}+1}$ ${\displaystyle 2^{n'}+1\geq 2^{2M+k}+1=D2^{2M}+1}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle ab}$ ${\displaystyle 2^{n}+1}$ ${\displaystyle A,B}$ ${\displaystyle g=2^{2M'}}$ ${\displaystyle g^{D/2}\equiv -1{\pmod {2^{n'}+1}}}$ ${\displaystyle g}$ ${\displaystyle D}$ ${\displaystyle 2^{n'}+1}$

Теперь мы берем дискретное преобразование Фурье массивов в кольце , используя корень из единицы для базиса Фурье, давая преобразованные массивы . Поскольку является степенью двойки, это можно сделать за логарифмическое время, используя быстрое преобразование Фурье . ${\displaystyle A,B}$ ${\displaystyle \mathbb {Z} /(2^{n'}+1)\mathbb {Z} }$ ${\displaystyle g}$ ${\displaystyle {\widehat {A}},{\widehat {B}}}$ ${\displaystyle D=2^{k}}$

Пусть (поточечное произведение) и вычислим обратное преобразование массива , снова используя корень из единицы . Массив теперь является сверткой массивов . Наконец, произведение получается путем вычисления ${\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}$ ${\displaystyle C}$ ${\displaystyle {\widehat {C}}}$ ${\displaystyle g}$ ${\displaystyle C}$ ${\displaystyle A,B}$ ${\displaystyle ab{\pmod {2^{n}+1}}}$ $${\displaystyle ab\equiv \sum _{j}C_{j}2^{Mj}\mod {2^{n}+1}.}$$

Этот базовый алгоритм можно улучшить несколькими способами. Во-первых, не обязательно хранить цифры с произвольной точностью, а только до битов, что дает более эффективное машинное представление массивов . Во-вторых, очевидно, что умножения в прямых преобразованиях являются простыми битовыми сдвигами. При некоторой осторожности также возможно вычислить обратное преобразование, используя только сдвиги. При соблюдении осторожности, таким образом, можно исключить любые истинные умножения из алгоритма, за исключением того, где оценивается поточечное произведение. Поэтому выгодно выбирать параметры так, чтобы это поточечное произведение могло быть выполнено эффективно, либо потому, что это одно машинное слово, либо с использованием некоторого оптимизированного алгоритма для умножения целых чисел (в идеале небольшого) количества слов. Таким образом, выбор параметров является важной областью для дальнейшей оптимизации метода. ${\displaystyle a,b}$ ${\displaystyle n'+1}$ ${\displaystyle A,B}$ ${\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}$ ${\displaystyle D,M}$ ${\displaystyle D,M}$

Подробности

Каждое число в системе счисления B можно записать в виде многочлена:

${\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}$

Более того, умножение двух чисел можно рассматривать как произведение двух многочленов:

${\displaystyle XY=\left(\sum _{i=0}^{N}{x_{i}B^{i}}\right)\left(\sum _{j=0}^{N}{y_{i}B^{j}}\right)}$

Потому что для : у нас есть свертка. ${\displaystyle B^{k}}$ ${\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{k-i}}}$

Используя БПФ ( быстрое преобразование Фурье ), используемое в оригинальной версии вместо НТТ ( теоретико-числовое преобразование ) ^[7] с правилом свертки; мы получаем

${\displaystyle {\hat {f}}(a*b)={\hat {f}}\left(\sum _{i=0}^{k}a_{i}b_{k-i}\right)={\hat {f}}(a)\bullet {\hat {f}}(b).}$

То есть; , где — соответствующий коэффициент в пространстве Фурье. Это также можно записать как: . ${\displaystyle C_{k}=a_{k}\bullet b_{k}}$ ${\displaystyle C_{k}}$ ${\displaystyle {\text{fft}}(a*b)={\text{fft}}(a)\bullet {\text{fft}}(b)}$

У нас одинаковые коэффициенты из-за линейности преобразования Фурье, а также потому, что эти полиномы состоят только из одного уникального члена на коэффициент:

${\displaystyle {\hat {f}}(x^{n})=\left({\frac {i}{2\pi }}\right)^{n}\delta ^{(n)}}$ и

${\displaystyle {\hat {f}}(a\,X(\xi )+b\,Y(\xi ))=a\,{\hat {X}}(\xi )+b\,{\hat {Y}}(\xi )}$

Правило свертки: ${\displaystyle {\hat {f}}(X*Y)=\ {\hat {f}}(X)\bullet {\hat {f}}(Y)}$

Мы свели нашу задачу свертки к задаче произведения с помощью БПФ.

Найдя БПФ полиномиальной интерполяции каждого , можно определить искомые коэффициенты. ${\displaystyle C_{k}}$

Этот алгоритм использует метод «разделяй и властвуй» для разделения проблемы на подзадачи.

Свертка по модуН

${\displaystyle c_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}}$, где . ${\displaystyle N(n)=2^{n}+1}$

Сдавая в аренду:

${\displaystyle a_{i}'=\theta ^{i}a_{i}}$и ${\displaystyle b_{j}'=\theta ^{j}b_{j},}$

где корень n-й ^{степени} , видно, что: ^[8] ${\displaystyle \theta ^{N}=-1}$

${\displaystyle {\begin{aligned}C_{k}&=\sum _{(i,j):i+j=k\equiv {\pmod {N(n)}}}a_{i}b_{j}=\theta ^{-k}\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}'b_{j}'\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}'b_{j}'+\sum _{(i,j):i+j=k+n}a_{i}'b_{j}'\right)\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=\sum _{(i,j):i+j=k}a_{i}b_{j}+\theta ^{n}\sum _{(i,j):i+j=k+n}a_{i}b_{j}.\end{aligned}}}$

Это значит, что можно использовать вес , а затем умножить на него. ${\displaystyle \theta ^{i}}$ ${\displaystyle \theta ^{-k}}$

Вместо использования веса, как на первом шаге рекурсии (когда ), можно вычислить: ${\displaystyle \theta ^{N}=-1}$ ${\displaystyle n=N}$

${\displaystyle C_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(N)}}}=\sum _{(i,j):i+j=k}a_{i}b_{j}-\sum _{(i,j):i+j=k+n}a_{i}b_{j}}$

В обычном БПФ, которое работает с комплексными числами, можно использовать:

$${\displaystyle \exp \left({\frac {2k\pi i}{n}}\right)=\cos {\frac {2k\pi }{n}}+i\sin {\frac {2k\pi }{n}},\qquad k=0,1,\dots ,n-1.}$$

${\displaystyle {\begin{aligned}C_{k}&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=e^{-i2\pi k/n}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}e^{i2\pi k/n}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}e^{i2\pi (n+k)/n}\right)\end{aligned}}}$

Однако БПФ также может использоваться как NTT ( теоретико-числовое преобразование ) в Шёнхаге–Штрассене. Это означает, что мы должны использовать θ для генерации чисел в конечном поле (например ). ${\displaystyle \mathrm {GF} (2^{n}+1)}$

Корень из единицы в конечном поле GF( r ) — это элемент a такой, что или . Например, GF( p ) , где p — простое число , дает . ${\displaystyle \theta ^{r-1}\equiv 1}$ ${\displaystyle \theta ^{r}\equiv \theta }$ ${\displaystyle \{1,2,\ldots ,p-1\}}$

Обратите внимание, что в и в . Для этих кандидатов, в рамках его конечного поля, и поэтому действуют так, как мы хотим . ${\displaystyle 2^{n}\equiv -1}$ ${\displaystyle \operatorname {GF} (2^{n}+1)}$ ${\displaystyle {\sqrt {2}}\equiv -1}$ ${\displaystyle \operatorname {GF} (2^{n+2}+1)}$ ${\displaystyle \theta ^{N}\equiv -1}$

Однако те же самые алгоритмы БПФ по-прежнему можно использовать, пока θ является корнем единицы конечного поля.

Чтобы найти преобразование FFT/NTT, делаем следующее:

${\displaystyle {\begin{aligned}C_{k}'&={\hat {f}}(k)={\hat {f}}\left(\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\right)\\[6pt]C_{k+k}'&={\hat {f}}(k+k)={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=n+2k}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=2k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(A_{k\leftarrow k}\right)\bullet {\hat {f}}(B_{k\leftarrow k})+{\hat {f}}(A_{k\leftarrow k+n})\bullet {\hat {f}}(B_{k\leftarrow k+n})\end{aligned}}}$

Первый продукт дает вклад в , для каждого k . Второй дает вклад в , из-за mod . ${\displaystyle c_{k}}$ ${\displaystyle c_{k}}$ ${\displaystyle (i+j)}$ ${\displaystyle N(n)}$

Чтобы сделать обратное:

${\displaystyle C_{k}=2^{-m}{\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$или ${\displaystyle C_{k}={\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$

в зависимости от того, требуется ли нормализация данных.

Для нормализации данных БПФ в определенном диапазоне выполняется умножение на , где , где m находится с помощью модульной мультипликативной обратной функции . ${\displaystyle 2^{-m}}$ ${\displaystyle {\frac {1}{n}}\equiv 2^{-m}{\bmod {N}}(n)}$

Подробности реализации

ПочемуН= 2М+ 1 модН

В алгоритме Шёнхаге–Штрассена . Это следует рассматривать как бинарное дерево, где есть значения в . Позволяя , для каждого K можно найти все и сгруппировать все пары в M различных групп. Использование для группировки пар посредством свертки является классической проблемой в алгоритмах. ^[9] ${\displaystyle N=2^{M}+1}$ ${\displaystyle 0\leq {\text{index}}\leq 2^{M}=2^{i+j}}$ ${\displaystyle K\in [0,M]}$ ${\displaystyle i+j=K}$ ${\displaystyle (i,j)}$ ${\displaystyle i+j=k}$ ${\displaystyle (i,j)}$

Имея это в виду, помогите нам сгруппировать в группы для каждой группы подзадач по глубине k в дереве с ${\displaystyle N=2^{M}+1}$ ${\displaystyle (i,j)}$ ${\displaystyle {\frac {M}{2^{k}}}}$ ${\displaystyle N=2^{\frac {M}{2^{k}}}+1}$

Обратите внимание, что для некоторого L. Это делает N числом Ферма . При выполнении mod мы получаем кольцо Ферма. ${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$ ${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$

Поскольку некоторые числа Ферма являются простыми числами Ферма, в некоторых случаях можно избежать вычислений.

Конечно, есть и другие N , которые можно было бы использовать с теми же преимуществами простого числа. Позволяя , можно получить максимальное число в двоичном числе с битами. — это число Мерсенна, которое в некоторых случаях является простым числом Мерсенна. Это естественный кандидат против числа Ферма ${\displaystyle N=2^{k}-1}$ ${\displaystyle k+1}$ ${\displaystyle N=2^{k}-1}$ ${\displaystyle N=2^{2^{L}}+1}$

В поисках другогоН

Выполнение нескольких расчетов mod против различных N может быть полезным при решении целочисленного произведения. Используя китайскую теорему об остатках , после разделения M на меньшие различные типы N , можно найти ответ умножения xy ^[10]

Числа Ферма и числа Мерсенна — это всего лишь два типа чисел, в так называемом обобщенном числе Ферма-Мерсенна (GSM); с формулой: ^[11]

${\displaystyle G_{q,p,n}=\sum _{i=1}^{p}q^{(p-i)n}={\frac {q^{pn}-1}{q^{n}-1}}}$

${\displaystyle M_{p,n}=G_{2,p,n}}$

В этой формуле — число Ферма, а — число Мерсенна. ${\displaystyle M_{2,2^{k}}}$ ${\displaystyle M_{p,1}}$

Эту формулу можно использовать для генерации наборов уравнений, которые можно использовать в китайской теореме об остатках (CRT): ^[12]

${\displaystyle g^{\frac {(M_{p,n}-1)}{2}}\equiv -1{\pmod {M_{p,n}}}}$, где g — число такое, что существует x , где , предполагая, что ${\displaystyle x^{2}\equiv g{\pmod {M_{p,n}}}}$ ${\displaystyle N=2^{n}}$

Кроме того; , где a — элемент, который генерирует элементы циклическим образом. ${\displaystyle g^{2^{(p-1)n}-1}\equiv a^{2^{n}-1}{\pmod {M_{p,n}}}}$ ${\displaystyle \{1,2,4,...2^{n-1},2^{n}\}}$

Если , где , то . ${\displaystyle N=2^{t}}$ ${\displaystyle 1\leq t\leq n}$ ${\displaystyle g_{t}=a^{(2^{n}-1)2^{n-t}}}$

Как выбратьКдля определенногоН

Следующая формула полезна для нахождения правильного K (количества групп, на которые нужно разделить N бит) при заданном размере бит N путем вычисления эффективности: ^[13]

${\displaystyle E={\frac {{\frac {2N}{K}}+k}{n}}}$ N — размер бита (используемый в ) на самом внешнем уровне. K задает группы битов, где . ${\displaystyle 2^{N}+1}$ ${\displaystyle {\frac {N}{K}}}$ ${\displaystyle K=2^{k}}$

n находится через N, K и k путем нахождения наименьшего x , такого, что ${\displaystyle 2N/K+k\leq n=K2^{x}}$

Если предположить, что эффективность выше 50%, а k очень мал по сравнению с остальной частью формулы, то получим ${\displaystyle {\frac {n}{2}}\leq {\frac {2N}{K}},K\leq n}$

${\displaystyle K\leq 2{\sqrt {N}}}$

Это означает: когда что-то очень эффективно; K ограничено сверху или асимптотически ограничено сверху ${\displaystyle 2{\sqrt {N}}}$ ${\displaystyle {\sqrt {N}}}$

Псевдокод

Следующий алогистик, стандартный модульный алгоритм умножения Шёнхаге-Штрассена (с некоторыми оптимизациями), можно найти в обзоре в ^[14]

1. Разделите оба входных числа a и b на n коэффициентов по s бит каждый.

   Используйте по крайней мере ⁠ ⁠ ${\displaystyle K+1}$ бит для их хранения,

   разрешить кодирование значения ⁠ ⁠ ${\displaystyle 2^{K}.}$
2. Взвесим оба вектора коэффициентов согласно (2.24) степенями θ , выполнив над ними циклические сдвиги.
3. Перемешайте коэффициенты ⁠ ⁠ ${\displaystyle a_{i}}$ и ⁠ ⁠ ${\displaystyle b_{j}}$ .
4. Оцените ⁠ ⁠ ${\displaystyle a_{i}}$ и ⁠ ⁠ ${\displaystyle b_{j}}$ . Умножение на степени ω является циклическим сдвигом.
5. Не делайте поточечных умножений ⁠ ⁠ ${\displaystyle c_{k}:=a_{k}b_{k}}$ в ⁠ ⁠ ${\displaystyle Z/(2^{K}+1)Z}$ . Если SMUL используется рекурсивно, укажите K в качестве параметра. В противном случае используйте какую-либо другую функцию умножения, например T3MUL, и затем выполните сокращение по модулю ⁠ ⁠ ${\displaystyle 2^{K}+1}$ .
6. Перемешайте коэффициенты произведения ⁠ ⁠ ${\displaystyle c_{k}}$ .
7. Оцените коэффициенты произведения ⁠ ⁠ ${\displaystyle c_{k}}$ .
8. Применяем противовесы к ⁠ ⁠ ${\displaystyle c_{k}}$ согласно (2.25). Поскольку ⁠ ⁠ ${\displaystyle \theta ^{2n}\equiv 1}$ следует, что ⁠ ⁠ ${\displaystyle \theta ^{-k}\equiv \theta ^{n-k}}$
9. Нормализуем ⁠ ⁠ ${\displaystyle c_{k}}$ с помощью ⁠ ⁠ ${\displaystyle 1/n\equiv 2^{-m}}$ (снова циклический сдвиг).
10. Сложите ⁠ ⁠ ${\displaystyle c_{k}}$ и размножьте переносы. Убедитесь, что правильно обрабатываете отрицательные коэффициенты.
11. Выполните сокращение по модулю ⁠ ⁠ ${\displaystyle 2^{N}+1}$ .

• T3MUL = умножение Тоома–Кука
• SMUL = умножение Шёнхаге – Штрассена
• Оценка = БПФ/ОБПФ

Дальнейшее изучение

Подробности реализации можно прочитать в книге « Prime Numbers: A Computational Perspective» . ^[15] Этот вариант несколько отличается от оригинального метода Шёнхаге тем, что он использует дискретное взвешенное преобразование для более эффективного выполнения негациклических сверток . Другим источником подробной информации является « The Art of Computer Programming» Кнута . ^[16]

Оптимизации

В этом разделе объясняется ряд важных практических оптимизаций при реализации Шёнхаге–Штрассена.

Использование другого алгоритма умножения, внутри алгоритма

Ниже определенной точки отсечения эффективнее использовать другие алгоритмы умножения, такие как умножение Тума–Кука . ^[17]

Трюк с квадратным корнем из 2

Идея заключается в использовании в качестве корня единицы порядка в конечном поле (это решение уравнения ), при взвешивании значений в подходе NTT (теоретико-числовое преобразование). Было показано, что это экономит 10% времени умножения целых чисел. ^[18] ${\displaystyle {\sqrt {2}}}$ ${\displaystyle 2^{n+2}}$ ${\displaystyle \mathrm {GF} (2^{n+2}+1)}$ ${\displaystyle \theta ^{2^{n+2}}\equiv 1{\pmod {2^{n+2}+1}}}$

трюк Гранлунда

Позволяя , можно вычислить и . В сочетании с CRT (китайской теоремой об остатках) для нахождения точных значений умножения uv ^[19] ${\displaystyle m=N+h}$ ${\displaystyle uv{\bmod {2^{N}+1}}}$ ${\displaystyle (u{\bmod {2^{h}}})(v{\bmod {2}}^{h})}$

Ссылки

1. Шёнхаге, Арнольд ; Штрассен, Волкер (1971). «Schnelle Multiplikation großer Zahlen» [Быстрое умножение больших чисел]. Вычисление (на немецком языке). 7 (3–4): 281–292. дои : 10.1007/BF02242355. S2CID  9738629.
2. Умножение Карацубы имеет асимптотическую сложность около , а умножение Тума–Кука имеет асимптотическую сложность около ${\displaystyle O(n^{1.58})}$ ${\displaystyle O(n^{1.46}).}$

   Van Meter, Rodney; Itoh, Kohei M. (2005). "Быстрое квантовое модульное возведение в степень". Physical Review . 71 (5): 052320. arXiv : quant-ph/0408006 . Bibcode : 2005PhRvA..71e2320V. doi : 10.1103/PhysRevA.71.052320. S2CID  14983569.

   Обсуждение практических точек пересечения между различными алгоритмами можно найти в: Обзор функций Magma V2.9, раздел арифметики. Архивировано 20 августа 2006 г. на Wayback Machine.

   Луис Карлос Коронадо Гарсия, «Может ли умножение Шёнхаге ускорить шифрование или дешифрование RSA? Архивировано», Технический университет, Дармштадт (2005)

   Библиотека GNU Multi-Precision использует его для значений длиной не менее 1728–7808 64-битных слов (от 33 000 до 150 000 десятичных цифр) в зависимости от архитектуры. См.:

   "Умножение БПФ (GNU MP 6.2.1)". gmplib.org . Получено 20 июля 2021 г. .

   "MUL_FFT_THRESHOLD". Уголок разработчиков GMP . Архивировано из оригинала 24 ноября 2010 г. Получено 3 ноября 2011 г.

   "MUL_FFT_THRESHOLD". gmplib.org . Получено 2021-07-20 .

3. Алгоритм Фюрера имеет асимптотическую сложность ${\textstyle O{\bigl (}n\cdot \log n\cdot 2^{\Theta (\log ^{*}n)}{\bigr )}.}$
   Фюрер, Мартин (2007). "Быстрое целочисленное умножение" (PDF) . Proc. STOC '07 . Симпозиум по теории вычислений, Сан-Диего, июнь 2007 г. стр. 57–66. Архивировано из оригинала (PDF) 2007-03-05.
   Фюрер, Мартин (2009). «Быстрое целочисленное умножение». Журнал SIAM по вычислениям . 39 (3): 979–1005. doi :10.1137/070711761. ISSN  0097-5397.

   Алгоритм Фюрера используется в библиотеке с открытым исходным кодом Basic Polynomial Algebra Subprograms (BPAS). См.: Covanov, Svyatoslav; Mohajerani, Davood; Moreno Maza, Marc; Wang, Linxiao (2019-07-08). "Big Prime Field FFT on Multi-core Processors". Труды Международного симпозиума по символьным и алгебраическим вычислениям 2019 года (PDF) . Пекин, Китай: ACM. стр. 106–113. doi :10.1145/3326229.3326273. ISBN 978-1-4503-6084-5. S2CID  195848601.

4. Харви, Дэвид; ван дер Хувен, Йорис (2021). "Целочисленное умножение за время O ( n log ⁡ n ) {\displaystyle O(n\log n)} " (PDF) . Анналы математики . Вторая серия. 193 (2): 563–617. doi :10.4007/annals.2021.193.2.4. MR  4224716. S2CID  109934776.
5. Этот метод используется в библиотеке ECM INRIA.
6. "ECMNET". members.loria.fr . Получено 2023-04-09 .
7. Беккер, Ханно; Хванг, Винсент; Дж. Канвишер, Маттиас; Панни, Лоренц (2022). «Эффективное умножение довольно малых целых чисел с использованием теоретико-числовых преобразований» (PDF) .
8. Людерс, Кристоф (2014). «Быстрое умножение больших целых чисел: реализация и анализ алгоритма DKSS». стр. 26.
9. Кляйнберг, Джон; Тардос, Ева (2005). Разработка алгоритмов (1-е изд.). Пирсон. п. 237. ИСБН 0-321-29535-8.
10. Годри, Пьеррик; Александр, Круппа; Пол, Циммерманн (2007). «Реализация алгоритма умножения больших целых чисел Шенхаге-Штрассена на основе GMP» (PDF) . п. 6.
11. С. Димитров, Васил; В. Куклев, Тодор; Д. Доневский, Борислав (1994). "Обобщенное преобразование Ферма-Мерсенна в теории чисел". стр. 2.
12. С. Димитров, Васил; В. Куклев, Тодор; Д. Доневский, Борислав (1994). "Обобщенное преобразование Ферма-Мерсенна в теории чисел". стр. 3.
13. Годри, Пьеррик; Круппа, Александр; Циммерманн, Пол (2007). «Реализация алгоритма умножения больших целых чисел Шенхаге-Штрассена на основе GMP» (PDF) . п. 2.
14. Людерс, Кристоф (2014). «Быстрое умножение больших целых чисел: реализация и анализ алгоритма DKSS». стр. 28.
15. R. Crandall & C. Pomerance. Простые числа – вычислительная перспектива . Второе издание, Springer, 2005. Раздел 9.5.6: Метод Шёнхаге, стр. 502. ISBN 0-387-94777-9 
16. Кнут, Дональд Э. (1997). "§ 4.3.3.C: Дискретные преобразования Фурье". Искусство программирования . Том 2: Получисленные алгоритмы (3-е изд.). Эддисон-Уэсли. С. 305–311. ISBN 0-201-89684-2.
17. Годри, Пьеррик; Круппа, Александр; Циммерманн, Пол (2007). «Реализация алгоритма умножения больших целых чисел Шенхаге-Штрассена на основе GMP» (PDF) . п. 7.
18. Годри, Пьеррик; Круппа, Александр; Циммерманн, Пол (2007). «Реализация алгоритма умножения больших целых чисел Шенхаге-Штрассена на основе GMP» (PDF) . п. 6.
19. Годри, Пьеррик; Круппа, Александр; Циммерманн, Пол (2007). «Реализация алгоритма умножения больших целых чисел Шенхаге-Штрассена на основе GMP» (PDF) . п. 6.