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

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

Изобретён Арнольдом Шёнхаге и Фолькером Штрассеном в 1971 году[2].

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

  • представляется как , а  — как , где ;
  • перемножаются многочлены и с помощью быстрого преобразования Фурье, результат — ;
  • применяются переносы через разряды: , то есть .

Также в алгоритме можно умножать по модулю чисел Ферма , если применять двоичную систему счисления.

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

Примечания

править
  1. Bürgisser P., Clausen M., Shokrollahi A. Algebraic Complexity Theory. — Berlin: Springer-Verlag, 1997. — 618 p. — ISBN 3-540-60582-7..
  2. Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Computing. — 1971. — № 7. — P. 281—292.
  3. Fürer M. Faster integer multiplication // STOC 2007 Proceedings. — 2007. — P. 57—66. Архивировано 25 апреля 2013 года.
  4. Meter van R., Itoh K. M. Fast quantum modular exponentiation // Physical Review A. — 2005. — Т. 71. Архивировано 7 февраля 2006 года.
  5. Overview of Magma V2.9 Features, arithmetic section Архивировано 20 августа 2006 года.: 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. Архивировано 29 декабря 2009 года.