Algoritmo Schönhage-Strassen

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido de de:Schönhage-Strassen-Algorithmus. Ajude e colabore com a tradução.
Ambox grammar.svg
Esta página ou secção precisa de correção ortográfico-gramatical.
Pode conter incorreções textuais, podendo ainda necessitar de melhoria em termos de vocabulário ou coesão, para atingir um nível de qualidade superior conforme o livro de estilo da Wikipédia. Se tem conhecimentos linguísticos, sinta-se à vontade para ajudar.

O Algoritmo Schönhage-Strassen ou Método de Multiplicação Schönhage - Strassen é um método rápido de multiplicação de 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 depois de 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. Obter 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 de o sistema de numeração ser de base 2 (sistema binário) podem ser feitas multiplicações em modulo, usando para 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 assintoticas 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 | editar código-fonte]

  1. Martin Fürer: Faster integer multiplication, 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: 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


Weblinks[editar | editar código-fonte]