Algoritmo Schönhage-Strassen

O Algoritmo Schönhage-Strassen ou Método de Multiplicação Schönhage-Strassen é um método rápido de multiplicação de números inteiros grandes. O método por trás do algoritmo consiste na Transformação Rápida de Fourier ou Transformada Rápida de Fourier, abreviada e conhecida pelo inglês como FFT (Fast Fourier Transform). Criada por Volker Schönhage e Arnold Strassen em 1971, este método requer operações $O(n\cdot \log {n})$ aritméticas e operações de $O(n\cdot \log {n}\cdot \log {\log {n}})$ bits de ordem assintótica, onde n é o número de dígitos no produto.

Na realidade, o método Schönhage-Strassen é um método de multiplicação de polinômios em uma variável. Ele representa, no algoritmo de multiplicação, os números como polinômios na base do próprio sistema de numeração; e após receber o resultado, faz a transferência por entre as fileiras. Por exemplo, para multiplicar 147 e 258 (em decimal), serão realizadas as seguintes operações:

Representação de 147 como x²+4x+7; e 258 como 2x²+5x+8, onde x = 10.
Multiplique polinômios x²+4x+7 e 2x²+5x+8 usando a transformada rápida de Fourier. Obtenha o produto dos polinômios 2x⁴+13x³+42x²+67x+56.
Ao fazer transferências entre as fileiras, temos 3x⁴+7x³+9x²+2x+6, ou seja, 37.926.

No caso do sistema de numeração ser de base 2 (sistema binário), podem ser feitas multiplicações em módulo, utilizando, para o módulo um, número de Fermat $2^{{2}^{n}}+1$ .

O Método Schönhage - Strassen foi considerado o método para multiplicações mais rápido em comparação de velocidades assintóticas entre 1971 e 2007, até que foi encontrado um novo método de estimativa de complexidade de multiplicação^[1]. Na prática, o método Schönhage - Strassen começa a extrapolar o tempo de outros métodos, tais como Karatsuba e Toom-Cook (uma espécie de generalização do método de Karatsuba) para inteiros de magnitude no intervalo $10^{10.000}$ a $10^{40.000}$ (de 10.000 a 40.000 dígitos decimais) ^[2]^[3]^[4]

Referências editar

↑ Martin Fürer: Faster integer multiplication Arquivado em 25 de abril de 2013, no Wayback Machine., STOC 2007 Proceedings, S. 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 Magma V2.9 Features: Arithmetic Section Arquivado em 20 de agosto de 2006, no Wayback Machine.: Discusses practical crossover points between various algorithms.
↑ L. C. Coronado García, Can Schönhage multiplication speed up the RSA encryption or decryption? University of Technology, 2005

Ligações externas editar

Página pessoal do Prof. Dr. Arnold Schönhage
Método de recorde mundial de cálculo é usado em homenagem póstuma (Comunicado à imprensa pela Universidade de Bonn em 21 de dezembro de 2004)

[1] Martin Fürer: Faster integer multiplication Arquivado em 25 de abril de 2013, no Wayback Machine., STOC 2007 Proceedings, S. 57–66.

[2] Rodney Van Meter and Kohei M. Itoh, "Fast quantum modular exponentiation", Physical Review A, Vol. 71 (2005).

[3] Overview of Magma V2.9 Features Magma V2.9 Features: Arithmetic Section Arquivado em 20 de agosto de 2006, no Wayback Machine.: Discusses practical crossover points between various algorithms.

[4] L. C. Coronado García, Can Schönhage multiplication speed up the RSA encryption or decryption? University of Technology, 2005

[1]

[2]

[3]

[4]