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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Метод умножения Шёнхаге — Штрассена (англ. 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 с помощью быстрого преобразования Фурье. Получаем x4 + 12x³ + 43x² + 54x + 7.
  • Делая переносы через разряды, получаем 2x4 + 6x³ + 8x² + 4x + 7, то есть 26847.

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

Метод Шёнхаге — Штрассена считался асимптотически быстрейшим методом с 1971 до 2007 годы, пока не был заявлен новый метод с лучшей оценкой сложности умножения.[3] На практике метод Шёнхаге — Штрассена начинает превосходить более ранние классические методы, такие как умножение Карацубы и алгоритм Тоома — Кука (обобщение метода Карацубы), начиная с целых чисел порядка 1010000—1040000 (от 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.

См. также[править | править вики-текст]