Algoritmo Schönhage-Strassen
Predefinição:Mais notas 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 aritméticas e operações de 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 2x4+13x³+42x²+67x+56.
- Ao fazer transferências entre as fileiras, temos 3x4+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 .
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 a (de 10.000 a 40.000 dígitos decimais) [2][3][4]
Referências
- ↑ Martin Fürer: Faster integer multiplication Predefinição:Wayback, 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 Predefinição:Wayback: 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
- 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)