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

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

Метод умножения Шёнхаге — Штрассена (англ. Schönhage–Strassen algorithm) — это асимптотически быстрый метод умножения для больших целых чисел. Является обобщением метода Карацубы с применением Быстрого Преобразования Фурье и умножения по модулю чисел Ферма $2^{2^n}+1$. Он был построен Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году.^[1]

Битовая сложность метода:

$O(N\cdot\log N\cdot\log\log N),$

а арифметическая сложность:^[2]

$O(N\cdot\log N).$

Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения^[3].

На практике, метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение Карацубы), начиная с целых чисел порядка $2^{2^{15}}$ до $2^{2^{17}}$ (от 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.

См. также

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