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

Метод умножения Шёнхаге-Штрассена это асимптотически быстрый метод умножения для больших целых чисел. Он был построен Арнольдом Шёнхаге и Фолькером Штрассеном в 1971.^[1]

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

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

а арифметическая сложность

$O(N \cdot \log N)$.^[2]

Этот метод использует быстрые преобразования Фурье в кольце из $2^{2^n}+1$ элементов.

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

На практике, метод Шёнхаге-Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома-Кука (обобщение Карацубы), начиная с целых чисел порядка $2^{2^{15}}$ до $2^{2^{17}}$ (от 10,000 до 40,000 десятичных знаков).^[4][5][6]

Ссылки

1. ↑ A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
2. ↑ Peter Bürgisser, Michael Clausen and Amin Shokrollahi, Algebraic Complexity Theory, 1997. Springer-Verlag, ISBN 3540605827.
3. ↑ Martin Fürer, "Faster integer multiplication", STOC 2007 Proceedings, pp. 57-66.
4. ↑ Rodney Van Meter and Kohei M. Itoh, "Fast quantum modular exponentiation", Physical Review A, Vol. 71 (2005).
5. ↑ Overview of Magma V2.9 Features, arithmetic section: Discusses practical crossover points between various algorithms.
6. ↑ Luis Carlos Coronado García, "Can Schönhage multiplication speed up the RSA encryption or decryption?", University of Technology, Darmstadt (2005)

См. также

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