thumb|350px|O algoritmo de Schönhage-Strassen baseia-se no método da transformada rápida de Fourier (FFT) para multiplicação de inteiros. Esta figura demonstra a multiplicação de 1234 × 5678 = 7006652 usando o método FFT simples. A base 10 é usada em vez da base 2w para fins ilustrativos. thumb|Schönhage (à direita) e Strassen (à esquerda) a jogar xadrez em Oberwolfach, 1979 O algoritmo de Schönhage-Strassen é um algoritmo de multiplicação assintoticamente rápido para grandes inteiros, publicado por Arnold Schönhage e Volker Strassen em 1971. Ele funciona aplicando recursivamente a transformada rápida de Fourier (FFT) sobre os inteiros módulo . A complexidade de bits no tempo de execução para multiplicar dois números de dígitos usando o algoritmo é de na notação Grande-O.

O algoritmo de Schönhage-Strassen foi o método de multiplicação assintoticamente mais rápido conhecido de 1971 até 2007. É assintoticamente mais rápido do que métodos mais antigos, como a multiplicação de Karatsuba e a Multiplicação de Toom-Cook, e começa a superá-los na prática para números além de cerca de 10 000 a 100 000 dígitos decimais.A multiplicação de Karatsuba tem uma complexidade assintótica de cerca de e a multiplicação de Toom-Cook tem uma complexidade assintótica de cerca de

Uma discussão sobre pontos de cruzamento práticos entre vários algoritmos pode ser encontrada em: Overview of Magma V2.9 Features, arithmetic section

Luis Carlos Coronado García, " Can Schönhage multiplication speed up the RSA encryption or decryption? Arquivado", University of Technology, Darmstadt (2005)

A GNU Multi-Precision Library utiliza-o para valores de pelo menos 1728 a 7808 palavras de 64 bits (33 000 a 150 000 dígitos decimais), dependendo da arquitetura. Ver: Em 2007, Martin Fürer publicou um algoritmo com uma complexidade assintótica mais rápida.O algoritmo de Fürer tem complexidade assintótica

O algoritmo de Fürer é usado na biblioteca de código aberto Basic Polynomial Algebra Subprograms (BPAS). Ver: Em 2019, David Harvey e Joris van der Hoeven demonstraram que a multiplicação de múltiplos dígitos tem uma complexidade teórica de ; contudo, o seu algoritmo tem fatores constantes que o tornam incrivelmente lento para qualquer problema prático concebível (ver algoritmo galáctico).

As aplicações do algoritmo de Schönhage-Strassen incluem grandes cálculos efetuados pelo seu próprio valor, tais como a Great Internet Mersenne Prime Search e as aproximações de , assim como aplicações práticas como a Fatoração de curvas elípticas de Lenstra através da Substituição de Kronecker, que reduz a multiplicação de polinómios à multiplicação de inteiros.Este método é utilizado na biblioteca ECM da INRIA.

Detalhes Todo o número na base B pode ser escrito como um polinómio:

Além disso, a multiplicação de dois números pode ser pensada como o produto de dois polinómios:

Uma vez que, para : , temos uma convolução.

Ao utilizar a FFT (Transformada Rápida de Fourier), usada na versão original em vez da NTT (Transformada teórica dos números ou de número teórico), com a regra da convolução, obtemos

Isto é, , onde é o coeficiente correspondente no espaço de Fourier. Isto também pode ser escrito como: .

Temos os mesmos coeficientes devido à linearidade sob a transformada de Fourier e porque estes polinómios consistem em apenas um termo único por coeficiente:

e

Regra da convolução:

Reduzimos o nosso problema de convolução a um problema de produto, através da FFT.

Ao encontrar a FFT da interpolação polinomial de cada , podemos determinar os coeficientes pretendidos.

Este algoritmo utiliza o método de divisão e conquista para dividir o problema em subproblemas.

Convolução módulo N , onde .

Considerando:

e

onde é a -ésima raiz, constata-se que:

Isto significa que se pode utilizar o peso e, em seguida, multiplicar por .

Em vez de usar o peso, dado que , no primeiro passo da recursão (quando ), pode-se calcular:

Numa FFT normal que opera sobre números complexos, utilizar-se-ia:

Contudo, a FFT também pode ser usada como uma NTT (Transformada teórica dos números) no algoritmo de Schönhage–Strassen. Isto implica que temos de usar para gerar números num corpo finito (por exemplo, ).

Uma raiz da unidade sob um corpo finito é um elemento tal que ou . Por exemplo, , onde é um número primo, resulta em .

Repare que em e em . Para estes candidatos, sob o seu corpo finito e, portanto, atuam da forma que pretendemos.

No entanto, os mesmos algoritmos de FFT ainda podem ser utilizados, desde que seja uma raiz da unidade de um corpo finito.

Para calcular a transformada FFT/NTT, fazemos o seguinte:

O primeiro produto contribui para , para cada . O segundo contribui para , devido a .

Para efetuar a inversa:

ou dependendo se os dados necessitam de ser normalizados.

Multiplica-se por para normalizar os dados da FFT para um intervalo específico, em que , onde é encontrado utilizando o inverso multiplicativo modular.

Detalhes de implementação

Por que N = 2 + 1 mod N [Image of a binary tree data structure]

No algoritmo de Schönhage-Strassen, . Isto deve ser pensado como uma árvore binária, onde se têm valores no intervalo . Ao definir , para cada é possível encontrar todos os , e agrupar todos os pares em M grupos diferentes. Utilizar para agrupar pares através de convolução é um problema clássico na área de algoritmos.

Tendo isto em mente, ajuda-nos a agrupar em grupos para cada grupo de subtarefas na profundidade de uma árvore com .

Repare que , para algum L. Isto faz de N um Número de Fermat. Ao aplicar o módulo , obtemos um anel de Fermat.

Dado que alguns números de Fermat são primos de Fermat, nalguns casos é possível evitar certos cálculos computacionais.

Existem outros N que poderiam ter sido utilizados, naturalmente, com as mesmas vantagens dos números primos. Ao definir , obtemos o número máximo num valor binário de bits. é um número de Mersenne, que nalguns casos também é um primo de Mersenne. É um candidato natural a par do número de Fermat .

Em busca de outro N

Efetuar vários cálculos modulares com diferentes valores de pode ser muito útil quando se trata de resolver o produto de inteiros. Ao utilizar o Teorema chinês dos restos, depois de dividir em tipos diferentes e mais pequenos de , é possível encontrar o resultado da multiplicação .

Os números de Fermat e os números de Mersenne são apenas dois tipos de números dentro daquilo a que se chama de Número Generalizado de Fermat-Mersenne (GSM); representados pela fórmula:

Nesta fórmula, é um número de Fermat, e é um número de Mersenne.

Esta fórmula pode ser utilizada para gerar sistemas de equações que, por sua vez, podem ser aplicados no CRT (Teorema chinês dos restos):

, onde é um número tal que existe um em que , assumindo

Além disso, , onde é um elemento que gera elementos em de forma cíclica.

Se , onde , então .

Como escolher K para um N específico

A seguinte fórmula é útil para encontrar um adequado (número de grupos nos quais dividir os bits) dado o tamanho em bits , calculando a sua eficiência:

. Aqui, é o tamanho em bits (o utilizado em ) no nível mais externo. fornece grupos de bits, onde .

O valor de é encontrado através de e ao procurar o menor tal que .

Se se assumir uma eficiência superior a 50%, e é muito pequeno em comparação com o resto da fórmula; o que resulta em:

Isto significa que: quando o método é muito eficaz, é limitado superiormente por ou assintoticamente limitado superiormente por .

Pseudocódigo

O algoritmo que se segue, o algoritmo padrão de Multiplicação Modular de Schönhage-Strassen (com algumas otimizações), é apresentado de forma genérica através de Dividir ambos os números de entrada e em coeficientes de bits cada um. Utilizar pelo menos bits para os armazenar, para permitir a codificação do valor Ponderar ambos os vetores de coeficientes de acordo com (2.24) com potências de , efetuando deslocamentos cíclicos (shifts) sobre eles. Reordenar (shuffle) os coeficientes e . Avaliar e . Multiplicações por potências de ω são realizadas como deslocamentos cíclicos. Efetuar multiplicações pontuais em . Se a SMUL for usada de forma recursiva, fornecer como parâmetro. Caso contrário, usar outra função de multiplicação como a T3MUL e reduzir módulo de seguida. Reordenar os coeficientes do produto . Avaliar os coeficientes do produto . Aplicar os contrapesos (counterweights) aos de acordo com (2.25). Como , conclui-se que . Normalizar os com (novamente um deslocamento cíclico). Somar os e propagar os transportes (carries). Certificar-se de tratar adequadamente os coeficientes negativos. Efetuar uma redução módulo .

T3MUL = Multiplicação de Toom–Cook SMUL = Multiplicação de Schönhage–Strassen Avaliar = FFT/IFFT Estudos adicionais Para obter mais detalhes de implementação, é recomendada a leitura do livro Prime Numbers: A Computational Perspective.R. Crandall & C. Pomerance. Prime Numbers – A Computational Perspective. Segunda Edição, Springer, 2005. Secção 9.5.6: Schönhage method, p. 502. Esta variante difere de certa forma do método original de Schönhage, na medida em que explora a transformada discreta ponderada para realizar convoluções negacíclicas de forma muito mais eficiente. Outra excelente fonte de informações detalhadas é o clássico The Art of Computer Programming de Knuth.

Otimizações

Esta seção explica uma série de otimizações práticas importantes na implementação do algoritmo de Schönhage-Strassen.

Uso de outros algoritmos de multiplicação dentro do algoritmo

Abaixo de um certo ponto de corte, é mais eficiente utilizar outros algoritmos de multiplicação, tais como a Multiplicação de Toom-Cook.

Truque da raiz quadrada de 2

A ideia é utilizar como uma raiz da unidade de ordem no corpo finito (é uma solução para a equação ), ao ponderar valores na abordagem NTT (transformada teórica dos números). Demonstrou-se que isto poupa 10% no tempo de multiplicação de inteiros.

Truque de Granlund

Ao definir , é possível calcular e em combinação com o CRT (Teorema chinês dos restos) para encontrar os valores exatos da multiplicação .

Referências

Categoria:Algoritmos Categoria:Aritmética Categoria:Teoria dos números