Convolução rápida em pequenos campos finitos

Quais são os métodos mais conhecidos para convolução cíclica de comprimento em um campo pequeno, ou seja, quando ? Estou particularmente interessado em campos de tamanho constante, ou até . As declarações e referências gerais de eficiência assintótica são muito apreciadas.$n$$|\mathbb{F}| \ll n$$\mathbb{F} = \mathbb{F}_2$

Antecedentes: Seja um campo . Pensamos nos vetores como tendo coordenadas indexadas por .$\mathbb{F}$$n > 0$$u \in \mathbb{F}^n$$\mathbb{Z}_n$

A convolução (cíclica) do comprimento sobre é a transformação que leva e gera , definida por com aritmética de índice sobre .$n$$\mathbb{F}$$u, v \in \mathbb{F}^n$$u * v \in \mathbb{F}^n$

Para executar a convolução cíclica em campos grandes, um método popular é usar o Teorema da Convolução para reduzir nosso problema ao executar Transformações Discretas de Fourier (DFTs) e usar um algoritmo FFT.

Para pequenos campos finitos, a DFT é indefinida porque não há ésima raiz primitiva da unidade. Pode-se contornar isso incorporando o problema em um campo finito maior, mas não está claro se esta é a melhor maneira de proceder. Mesmo se seguirmos esse caminho, seria bom saber se alguém já trabalhou nos detalhes (por exemplo, escolhendo qual campo maior usar e qual algoritmo FFT aplicar).$n$$^*$

Adicionado:

$^*$ Por 'encaixar' o nosso convolução, eu uma média de duas coisas. Primeira opção: pode-se passar para um campo de extensão no qual as raízes primitivas desejadas da unidade estão unidas e fazer a convolução lá.

Segunda opção: se nosso campo inicial for cíclico, pode-se passar para um campo cíclico de característica maior - suficientemente grande que se considerarmos nossos vetores como , não ocorre "envolvente". (Estou sendo informal, mas pense em como, para calcular uma convolução em F 2 , podemos claramente fazer a mesma convolução em Z e, em seguida, obter as respostas mod 2.)$\mathbb{F}_{p'}$$\mathbb{F}_{p'}$
$\mathbb{F}_2$$\mathbb{Z}$

Também adicionado:

Muitos algoritmos para FFT e problemas relacionados funcionam especialmente bem para valores "agradáveis" de (e eu gostaria de entender melhor a situação com isso). $n$

Mas se alguém não tenta tirar proveito dos valores especiais de , o problema da convolução cíclica é basicamente equivalente (por reduções fáceis envolvendo explosão linear em $n$$n$ ) à convolução comum; isso, por sua vez, é equivalente à multiplicação de polinômios com coeficientes acima de . $\mathbb{F}_p$

Por essa equivalência, pode-se usar resultados em, por exemplo, este artigo de von zur Gathen e Gerhard (construindo sobre o trabalho de Cantor), que usam uma abordagem de campo de extensão para obter uma complexidade de circuito vinculada . Eles não indicam seus limites de uma maneira especialmente clara na IMO, mas o limite é pior que n ⋅ log 2 n, mesmo para $\tilde{O}_p(n)$$n \cdot \log^2 n$ . Alguém pode fazer melhor?$\mathbb{F}_2$

Um recente artigo de Alexey Pospelov parece dar o estado da arte. (Não é o primeiro a alcançar os limites que citarei, mas os alcança de maneira unificada para campos arbitrários e, igualmente importante, indica claramente os limites, consulte a p. 3.)

podemos multiplicar dois degree- n polinómios mais de um campo arbitrária M utilizando O ( N log N ) multiplicações em F e S ( N log N log log n ) adições em F . Isso se deve originalmente a Schonhage-Strassen (para char. ≠ 2 ) e Schonhage para char. 2. Como mencionei, isso implica os mesmos limites para a convolução cíclica. Pospelov também afirma: "No momento, não temos conhecimento de nenhum algoritmo com um limite superior [acima] que não seja baseado em aplicativos DFT consecutivos ..."$\bullet$$n$$\mathbb{F}$$O(n \log n)$$\mathbb{F}$$O(n \log n \log \log n)$$\mathbb{F}$$\neq 2$

Cantor e Kaltofen generalizada estes resultados, mostrando os limites segure por álgebras arbitrárias (e não apenas campos).$\bullet$

Se F suporta Transformada Discreta de Fourier de ordem apropriada, isto é, se F tem uma primitiva N -ésimo raiz da unidade, onde N é suficientemente grande (penso N = S ( n ) sufixos) e N é uma potência de dois ou três , então podemos fazer a multiplicação polinomial com O ( n ) multiplicações e O ( n log n $\bullet$$\mathbb{F}$$\mathbb{F}$$N$$N$$N = O(n)$$N$$O(n)$$O(n \log n)$ adições. Várias outras melhorias são possíveis para campos com outras propriedades especiais.

Parece ser plausível, mas desconhecido, se a recentemelhoria deFurerna multiplicação de números inteiros ($\bullet$ reprovado de uma forma diferente por De et al.) Pode ajudar a levar a algoritmos de multiplicação mais rápida polinomiais, campos sobre finitos dizer. Alguém pode comentar?

A tese de Todd Mateer também parece ser um excelente recurso para entender a literatura da FFT e as aplicações para a multiplicação polinomial (obrigado Jug!); mas você precisa cavar mais para encontrar o que está procurando.