Schnelle Faltung über kleine endliche Felder

Was sind die bekanntesten Methoden für die zyklische Faltung der Länge $n$ über ein kleines Feld, dh wenn $|\mathbb{F}| \ll n$ ? Ich interessiere mich besonders für Felder mit konstanter Größe oder sogar $\mathbb{F} = \mathbb{F}_2$ . Allgemeine Aussagen und Referenzen zur asymptotischen Effizienz werden sehr geschätzt.

Hintergrund: Sei $\mathbb{F}$ ein Feld und $n > 0$ . Wir denken an Vektoren $u \in \mathbb{F}^n$ mit durch indizierten Koordinaten $\mathbb{Z}_n$.

Die (zyklische) Faltung der Länge über F ist die Transformation, die u , v ∈ F n nimmt und u ∗ v ∈ F n ausgibt , definiert durch mit über .$n$$\mathbb{F}$$u, v \in \mathbb{F}^n$$u * v \in \mathbb{F}^n$Z

Um eine zyklische Faltung über große Felder durchzuführen, besteht eine beliebte Methode darin, den Faltungssatz zu verwenden, um unser Problem auf die Durchführung diskreter Fouriertransformationen (DFTs) und die Verwendung eines FFT-Algorithmus zu reduzieren.

Für kleine endliche Felder ist die DFT undefiniert, weil es keine primitive te Einheitswurzel gibt. Man kann dies durch die Einbettung zu umgehen * das Problem in einem größeren endlichen Körper, aber es ist nicht klar , dass dies der beste Weg ist , um fortzufahren. Selbst wenn wir diesen Weg einschlagen, wäre es schön zu wissen, ob jemand die Details bereits ausgearbeitet hat (zum Beispiel, welches größere Feld verwendet und welcher FFT-Algorithmus angewendet werden soll).$n$$^*$

Hinzugefügt:

$^*$ Mit "Einbetten" unserer Faltung meine ich eines von zwei Dingen. Erste Option: Man könnte zu einem Erweiterungsfeld übergehen, in dem sich die gewünschten primitiven Wurzeln der Einheit anschließen, und dort die Faltung durchführen.

Zweite Option: Wenn unser Startfeld zyklisch ist, könnte man zu einem zyklischen Feld größerer Charakteristik übergehen - groß genug, wenn wir unsere Vektoren als in liegend betrachten. tritt kein "Wraparound" auf. (Ich bin informell, aber denke nur darüber nach, wie wir, um eine Faltung über zu berechnen , dieselbe Faltung über , und nehme dann die Antworten Mod 2.) F p ' F 2 $\mathbb{F}_{p'}$$\mathbb{F}_{p'}$
$\mathbb{F}_2$$\mathbb{Z}$

Auch hinzugefügt:

Viele Algorithmen für FFT und verwandte Probleme funktionieren besonders gut für 'nette' Werte von (und ich möchte die Situation damit besser verstehen). $n$

Wenn man aber nicht versucht, spezielle Werte von auszunutzen , ist das Problem der zyklischen Faltung im Grunde genommen (durch einfache Verkleinerung mit linearer Aufblähung in ) gleichbedeutend mit der normalen Faltung; Dies entspricht wiederum der Multiplikation von Polynomen mit Koeffizienten über . n F$n$$n$$\mathbb{F}_p$

Durch diese Äquivalenz kann man Ergebnisse zB in dieser Arbeit von zur Gathen und Gerhard (basierend auf Cantor) verwenden, die einen Extension-Field-Ansatz verwenden, um eine Schaltungskomplexität zu erhalten, die von . Sie geben ihre Grenzen nicht besonders deutlich an, IMO, aber die Grenze ist schlimmer als selbst für . Kann man es besser machen?n⋅log2nF$\tilde{O}_p(n)$$n \cdot \log^2 n$$\mathbb{F}_2$

Ein kürzlich veröffentlichter Artikel von Alexey Pospelov scheint den neuesten Stand der Technik zu vermitteln. (Es ist nicht der erste, der die Grenzen erreicht, die ich zitiere, aber es erreicht sie auf einheitliche Weise für beliebige Felder, und ebenso wichtig ist, dass es die Grenzen klar angibt, siehe S. 3.)

Wir können zwei Multiplizier Grad- n Polynome über einen beliebigen Bereich F unter Verwendung von O ( n log n ) Multiplikationen in F und O ( n log n log log n ) Additionen in F . Dies liegt ursprünglich an Schönhage-Strassen (für char. ≠ 2 ) und Schönhage für char. 2. Wie ich bereits erwähnte, impliziert dies die gleichen Grenzen für die zyklische Faltung. Pospelov erklärt außerdem: "Derzeit sind uns keine Algorithmen mit einer Obergrenze von [den oben genannten] bekannt, die nicht auf aufeinanderfolgenden DFT-Anwendungen basieren ..."$\bullet$$n$$\mathbb{F}$$O(n \log n)$$\mathbb{F}$$O(n \log n \log \log n)$$\mathbb{F}$$\neq 2$

$\bullet$

$\bullet$$\mathbb{F}$$\mathbb{F}$$N$$N$$N = O(n)$$N$$O(n)$$O(n \log n)$

$\bullet$

Todd Mateers These scheint auch eine hervorragende Quelle zu sein, um die FFT-Literatur und Anwendungen für die Polynom-Multiplikation zu verstehen (danke Jug!). Aber Sie müssen mehr graben, um das zu finden, wonach Sie suchen.