Szybki splot nad małymi skończonymi polami

Jakie są najbardziej znane metody cyklicznego splotu długości na małym polu, tj. Kiedy | F | « N ? Szczególnie interesują mnie pola o stałej wielkości, a nawet F = F 2 . Doceniane są ogólne stwierdzenia i referencje dotyczące skuteczności asymptotycznej.$n$$|\mathbb{F}| \ll n$$\mathbb{F} = \mathbb{F}_2$

Tło: Niech będzie polem, a n > 0 . Uważamy, że wektory u ∈ F n mają współrzędne indeksowane przez Z n .$\mathbb{F}$$n > 0$$u \in \mathbb{F}^n$$\mathbb{Z}_n$

(Cyklicznego) splot o długości nad F jest transformacja przy u , v ∈ M n i wyprowadzania u * v ∈ f n , określone przez ( u * v ) ı : = Σ J ∈ Z n v j U ı - j , z arytmetyką indeksu ponad Z n .$n$$\mathbb{F}$$u, v \in \mathbb{F}^n$$u * v \in \mathbb{F}^n$

Aby przeprowadzić cykliczne splatanie na dużych polach, popularną metodą jest użycie twierdzenia o konwolucji, aby zredukować nasz problem do wykonywania dyskretnych transformacji Fouriera (DFT) i przy użyciu algorytmu FFT.

W przypadku małych pól skończonych DFT jest niezdefiniowany, ponieważ nie ma prymitywnego pierwiastka jedności. Można obejść ten problem poprzez osadzenie * problem w większym zakresie skończonej, ale nie jest jasne, że jest to najlepszy sposób, aby kontynuować. Nawet gdybyśmy wybrali tę trasę, dobrze byłoby wiedzieć, czy ktoś już opracował szczegóły (na przykład wybierając większe pole do zastosowania i który algorytm FFT zastosować).$n$$^*$

Dodany:

„Osadzając” nasz splot, mam na myśli jedną z dwóch rzeczy. Pierwsza opcja: można przejść do pola rozszerzenia, w którym sąsiadują pożądane prymitywne pierwiastki jedności, i dokonać tam splotu. $^*$

Druga opcja: jeśli nasze pole początkowe jest cykliczne, można przejść do pola cyklicznego o większej charakterystyce - wystarczająco dużej, że jeśli weźmiemy pod uwagę nasze wektory leżące w F p ′ , nie występuje „zawinięcie”. (Jestem nieformalny, ale pomyślcie tylko, jak obliczyć splot nad F 2 , możemy oczywiście zrobić to samo splot nad Z , a następnie wziąć odpowiedzi mod 2.)$\mathbb{F}_{p'}$$\mathbb{F}_{p'}$
$\mathbb{F}_2$$\mathbb{Z}$

Dodano również:

Wiele algorytmów dla FFT i powiązanych problemów działa szczególnie dobrze dla „ładnych” wartości (i chciałbym lepiej zrozumieć sytuację). $n$

Ale jeśli nie spróbuje się skorzystać ze specjalnych wartości , problem cyklicznego splotu jest w zasadzie równoważny (dzięki łatwym redukcjom obejmującym liniowe powiększenie w n ) do zwykłego splotu; To z kolei jest równa mnożenia wielomianów współczynnikach ponad F p . $n$$n$$\mathbb{F}_p$

Dzięki tej równoważności można wykorzystać wyniki np. W pracy von Zura Gathena i Gerharda (bazując na pracy Cantora), którzy stosują podejście pola rozszerzenia, aby uzyskać granicę złożoności obwodu . Nie podają swoich granic w szczególnie jasny sposób IMO, ale granica jest gorsza niż n ⋅ log 2 n nawet dla F 2 . Czy można zrobić lepiej?$\tilde{O}_p(n)$$n \cdot \log^2 n$$\mathbb{F}_2$

Ostatni artykuł Aleksieja Pospelowa wydaje się przedstawiać najnowszy stan wiedzy. (Nie jest to pierwszy, który osiąga granice, które zacytuję, ale osiąga je w ujednolicony sposób dla dowolnych pól, i co równie ważne, wyraźnie określa granice, patrz str. 3.)

Możemy pomnożyć dwawielomiany stopnia n przez dowolne pole F, używając$\bullet$$n$$\mathbb{F}$ mnożenia w F i O ( n log n log log n ) dodatków w F . Jest to pierwotnie spowodowane Schonhage-Strassen (dla char. ≠ 2 ) i Schonhage dla char. 2. Jak wspomniałem, oznacza to takie same granice dla cyklicznego splotu. Pospelov stwierdza również: „Obecnie nie znamy żadnych algorytmów z górną granicą [powyższego], które nie są oparte na kolejnych aplikacjach DFT ...”$O(n \log n)$$\mathbb{F}$$O(n \log n \log \log n)$$\mathbb{F}$$\neq 2$

$\bullet$

Jeśli F obsługuje dyskretną transformatę Fouriera odpowiedniej kolejności, to znaczy, jeśli F ma prymitywne$\bullet$$\mathbb{F}$$\mathbb{F}$$N$$N$$N = O(n)$$N$$O(n)$$O(n \log n)$

$\bullet$

Todd Mateer jest teza wydaje się również jak doskonałe źródło do zrozumienia literatury FFT oraz aplikacje do mnożenia wielomianu (dzięki Jug!); ale musisz kopać więcej, aby znaleźć to, czego szukasz.