Algoritmo Schönhage-Strassen
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.
Todo o número na base B pode ser escrito como um polinómio: X = ∑ i = 0 N x i B i {\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}} Além disso, a multiplicação de dois números pode ser pensada como o produto de dois polinómios: X Y = ( ∑ i = 0 N x i B i ) ( ∑ j = 0 N y i B j ) {\displaystyle XY=\left(\sum _{i=0}^{N}{x_{i}B^{i}}\right)\left(\sum _{j=0}^{N}{y_{i}B^{j}}\right)} Uma vez que, para B k {\displaystyle B^{k}} : c k = ∑ ( i , j ) : i + j = k a i b j = ∑ i = 0 k a i b k − i {\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{k-i}}} , 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 f ^ ( a ∗ b ) = f ^ ( ∑ i = 0 k a i b k − i ) = f ^ ( a ) ∙ f ^ ( b ) . {\displaystyle {\hat {f}}(a*b)={\hat {f}}\left(\sum _{i=0}^{k}a_{i}b_{k-i}\right)={\hat {f}}(a)\bullet {\hat {f}}(b).} Isto é, C k = a k ∙ b k {\displaystyle C_{k}=a_{k}\bullet b_{k}} , onde C k {\displaystyle C_{k}} é o coeficiente correspondente no espaço de Fourier. Isto também pode ser escrito como: fft ( a ∗ b ) = fft ( a ) ∙ fft ( b ) {\displaystyle {\text{fft}}(a*b)={\text{fft}}(a)\bullet {\text{fft}}(b)} .
Convolução módulo N
c k = ∑ ( i , j ) : i + j ≡ k ( mod N ( n ) ) a i b j {\displaystyle c_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}} , onde N ( n ) = 2 n + 1 {\displaystyle N(n)=2^{n}+1} . a i ′ = θ i a i {\displaystyle a_{i}'=\theta ^{i}a_{i}} e b j ′ = θ j b j , {\displaystyle b_{j}'=\theta ^{j}b_{j},} onde θ N = − 1 {\displaystyle \theta ^{N}=-1} é a n {\displaystyle n} -ésima raiz, constata-se que: C k = ∑ ( i , j ) : i + j ≡ k ( mod N ( n ) ) a i b j = θ − k ∑ ( i , j ) : i + j ≡ k ( mod N ( n ) ) a i ′ b j ′ = θ − k ( ∑ ( i , j ) : i + j = k a i ′ b j ′ + ∑ ( i , j ) : i + j = k + n a i ′ b j ′ ) = θ − k ( ∑ ( i , j ) : i + j = k a i b j θ k + ∑ ( i , j ) : i + j = k + n a i b j θ n + k ) = ∑ ( i , j ) : i + j = k a i b j + θ n ∑ ( i , j ) : i + j = k + n a i b j . {\displaystyle {\begin{aligned}C_{k}&=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}=\theta ^{-k}\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}'b_{j}'\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}'b_{j}'+\sum _{(i,j):i+j=k+n}a_{i}'b_{j}'\right)\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=\sum _{(i,j):i+j=k}a_{i}b_{j}+\theta ^{n}\sum _{(i,j):i+j=k+n}a_{i}b_{j}.\end{aligned}}}
Por que N = 2M + 1 mod N
No algoritmo de Schönhage-Strassen, N = 2 M + 1 {\displaystyle N=2^{M}+1} . Isto deve ser pensado como uma árvore binária, onde se têm valores no intervalo 0 ≤ índice ≤ 2 M = 2 i + j {\displaystyle 0\leq {\text{índice}}\leq 2^{M}=2^{i+j}} . Ao definir K ∈ [ 0 , M ] {\displaystyle K\in [0,M]} , para cada K {\displaystyle K} é possível encontrar todos os i + j = K {\displaystyle i+j=K} , e agrupar todos os pares ( i , j ) {\displaystyle (i,j)} em M grupos diferentes. Utilizar i + j = k {\displaystyle i+j=k} para agrupar pares ( i , j ) {\displaystyle (i,j)} através de convolução é um problema clássico na área de algoritmos. Tendo isto em mente, N = 2 M + 1 {\displaystyle N=2^{M}+1} ajuda-nos a agrupar ( i , j ) {\displaystyle (i,j)} em M 2 k {\displaystyle {\frac {M}{2^{k}}}} grupos para cada grupo de subtarefas na profundidade k {\displaystyle k} de uma árvore com N = 2 M 2 k + 1 {\displaystyle N=2^{\frac {M}{2^{k}}}+1} .
Como escolher K para um N específico
A seguinte fórmula é útil para encontrar um K {\displaystyle K} adequado (número de grupos nos quais dividir os N {\displaystyle N} bits) dado o tamanho em bits N {\displaystyle N} , calculando a sua eficiência: E = 2 N K + k n {\displaystyle E={\frac {{\frac {2N}{K}}+k}{n}}} . Aqui, N {\displaystyle N} é o tamanho em bits (o utilizado em 2 N + 1 {\displaystyle 2^{N}+1} ) no nível mais externo. K {\displaystyle K} fornece N K {\displaystyle {\frac {N}{K}}} grupos de bits, onde K = 2 k {\displaystyle K=2^{k}} . O valor de n {\displaystyle n} é encontrado através de N , K {\displaystyle N,K} e k {\displaystyle k} ao procurar o menor x {\displaystyle x} tal que 2 N / K + k ≤ n = K 2 x {\displaystyle 2N/K+k\leq n=K2^{x}} .
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
Estudos adicionais
Para obter mais detalhes de implementação, é recomendada a leitura do livro Prime Numbers: A Computational Perspective. 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.
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 2 {\displaystyle {\sqrt {2}}} como uma raiz da unidade de ordem 2 n + 2 {\displaystyle 2^{n+2}} no corpo finito G F ( 2 n + 2 + 1 ) {\displaystyle \mathrm {GF} (2^{n+2}+1)} (é uma solução para a equação θ 2 n + 2 ≡ 1 ( mod 2 n + 2 + 1 ) {\displaystyle \theta ^{2^{n+2}}\equiv 1{\pmod {2^{n+2}+1}}} ), 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 m = N + h {\displaystyle m=N+h} , é possível calcular u v mod 2 N + 1 {\displaystyle uv{\bmod {2^{N}+1}}} e ( u mod 2 h ) ( v mod 2 h ) {\displaystyle (u{\bmod {2^{h}}})(v{\bmod {2^{h}}})} em combinação com o CRT (Teorema chinês dos restos) para encontrar os valores exatos da multiplicação u v {\displaystyle uv} .
