Метод умножения Шёнхаге-Штрассена
- Метод умножения Шёнхаге-Штрассена
-
Метод умножения Шёнхаге-Штрассена это асимптотически быстрый метод умножения для больших целых чисел. Он был построен Арнольдом Шёнхаге и Фолькером Штрассеном в 1971.[1]
Битовая сложность метода есть
,
а арифметическая сложность
.[2]
Этот метод использует быстрые преобразования Фурье в кольце из 
элементов.
Метод Шёнхаге-Штрассена считался асимптотически быстрейшим методом с 1971 до 2007, когда был заявлен новый метод с лучшей оценкой сложности умножения[3]
На практике, метод Шёнхаге-Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома-Кука (обобщение Карацубы), начиная с целых чисел порядка 
до 
(от 10,000 до 40,000 десятичных знаков).[4][5][6]
Ссылки
- ↑ A. Schönhage and V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), pp. 281–292.
- ↑ Peter Bürgisser, Michael Clausen and Amin Shokrollahi, Algebraic Complexity Theory, 1997. Springer-Verlag, ISBN 3540605827.
- ↑ Martin Fürer, "Faster integer multiplication", STOC 2007 Proceedings, pp. 57-66.
- ↑ Rodney Van Meter and Kohei M. Itoh, "Fast quantum modular exponentiation", Physical Review A, Vol. 71 (2005).
- ↑ Overview of Magma V2.9 Features, arithmetic section: Discusses practical crossover points between various algorithms.
- ↑ Luis Carlos Coronado García, "Can Schönhage multiplication speed up the RSA encryption or decryption?", University of Technology, Darmstadt (2005)
См. также
Wikimedia Foundation.
2010.
Полезное
Смотреть что такое "Метод умножения Шёнхаге-Штрассена" в других словарях:
Метод умножения Шёнхаге — Штрассена — Метод умножения Шёнхаге Штрассена (англ. Schönhage–Strassen algorithm) это асимптотически быстрый метод умножения для больших целых чисел. Является обобщением метода Карацубы с применением Быстрого Преобразования Фурье и умножения по… … Википедия
Метод умножения Шёнхаге — Метод умножения Шёнхаге Штрассена (англ. Schönhage–Strassen algorithm) быстрый метод умножения больших целых чисел. Основной идеей алгоритма является быстрое преобразование Фурье. Он был построен Арнольдом Шёнхаге и Фолькером… … Википедия
Алгоритм Фюрера — (англ. Fürer’s algorithm) быстрый метод умножения больших целых чисел. Алгоритм был построен в 2007 году швейцарским математиком Мартином Фюрером[1] из университета штата Пенсильвания как асимптотически более быстрый алгоритм, чем его… … Википедия
Умножение Карацубы — метод быстрого умножения, который позволяет перемножать два n значных числа со сложностью вычисления: Этот подход открыл новое направление в вычислительной математике [1][2]. Содержание 1 История … Википедия
Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и … Википедия
Карацуба — Карацуба, Анатолий Алексеевич Карацуба Анатолий Алексеевич Дата рождения: 31 января 1937(1937 01 31) … Википедия
Карацуба, Анатолий Алексеевич — Карацуба Анатолий Алексеевич Дата рождения: 31 января 1937 … Википедия
Быстрые алгоритмы — Значимость предмета статьи поставлена под сомнение. Пожалуйста, покажите в статье значимость её предмета, добавив в неё доказательства значимости по частным критериям значимости или, в случае если частные критерии значимости для… … Википедия
Быстрое умножение — Быстрое умножение общее название для нескольких быстрых алгоритмов умножения больших чисел. Методы быстрого умножения послужили толчком к развитию отдельной области информатики, занимающейся быстрыми алгоритмами. История … Википедия
Тест Люка — Тест Люка Лемера эффективный тест простоты для чисел Мерсенна. Благодаря этому тесту самые большие простые числа всегда были числами Мерсенна даже задолго до появления компьютеров.[1] Содержание 1 История 2 Тест 3 … Википедия
