Метод умножения Шёнхаге

Метод умножения Шёнхаге — Штрассена (англ. Schönhage–Strassen algorithm) — быстрый метод умножения больших целых чисел. Основной идеей алгоритма является быстрое преобразование Фурье. Он был построен Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году.^[1] Метод требует O(N·logN·log logN) битовых операций, где N — количество двоичных цифр в произведении.^[2]

Фактически, метод Шёнхаге — Штрассена является методом умножения многочленов от одной переменной. Он превращается в алгоритм умножения чисел, если эти числа представить как многочлены от основы системы счисления, а после получения результата сделать переносы через разряды. Например, для перемножения 157 и 171 (в десятичной системе счисления) мы выполняем следующие операции.

• Представляем 157 как x²+5x+7, а 171 — как x²+7x+1, где x=10.
• Перемножаем многочлены x²+5x+7 и x²+7x+1 с помощью быстрого преобразования Фурье. Получаем x⁴+12x³+43x²+54x+7.
• Делая переносы через разряды, получаем 2x⁴+6x³+8x²+4x+7, то есть 26847.

Также в алгоритме Шёнхаге — Штрассена можно умножать по модулю чисел Ферма $2^{2^n}+1$, если применять двоичную систему счисления.

Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения.^[3] На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка 10¹⁰⁰⁰⁰—10⁴⁰⁰⁰⁰ (от 10 000 до 40 000 десятичных знаков).^[4][5][6]

Примечания

1. ↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — P. 281—292.
2. ↑ Bürgisser P., Clausen M., Shokrollahi A. Algebraic Complexity Theory. — Berlin: Springer-Verlag, 1997. — 618 p. — ISBN 3-540-60582-7.
3. ↑ Fürer M. Faster integer multiplication // STOC 2007 Proceedings. — 2007. — P. 57—66.
4. ↑ Meter van R., Itoh K. M. Fast quantum modular exponentiation // Physical Review A. — 2005. — Т. 71.
5. ↑ Overview of Magma V2.9 Features, arithmetic section: Discusses practical crossover points between various algorithms.
6. ↑ Coronado García L. C. Can Schönhage multiplication speed up the RSA encryption or decryption? // University of Technology. — Darmstadt, 2005.

См. также

• Сложность вычисления (битовая)
• Быстрые алгоритмы
• АГС метод Гаусса
• Метод БВЕ
• Алгоритм Фюрера