Znajdź pozostałą część dużego stałego wielomianu po podzieleniu przez niewielki nieznany wielomian

Załóżmy, że działamy w polu skończonym. Otrzymujemy duży stały wielomian p (x) (powiedzmy stopnia 1000) nad tym polem. Ten wielomian jest znany wcześniej i możemy wykonywać obliczenia przy użyciu dużej ilości zasobów w „fazie początkowej”. Wyniki te mogą być przechowywane w stosunkowo małych tabelach przeglądowych.

Pod koniec „fazy początkowej” otrzymamy niewielki nieznany wielomian q (x) (powiedzmy stopnia 5 lub mniejszego).

Czy istnieje szybki sposób na obliczenie p (x) mod q (x), biorąc pod uwagę, że możemy wykonywać skomplikowane obliczenia w „fazie początkowej”? Jednym oczywistym sposobem jest obliczenie p (x) mod q (x) dla wszystkich możliwych wartości q (x). Czy jest na to lepszy sposób?

Poniższe algorytmy działają dobrze, jeśli podstawowe pole ma bardzo małe zamówienie $s$.

Załóżmy, że wiemy $q$ jest nieredukowalny, o stałym stopniu $d$. Następnie mod$q$, wiemy $x^{s^d} = x$trzyma. Dlatego wystarczy wstępnie obliczyć .$p(x) \mod x^{s^d} - x$

Zasadniczo może rozkładać się na iloczyn wielomianów nieredukowalnych . W tym przypadku podobny argument dotyczy obliczania modulo każdego osobno, a następnie łączenia wyników razem. Więc naprawdę musimy obliczyć dla każdego .$q(x)$$q = q_1 \dots q_r$$p$$q_1, \dots, q_r$$p(x) \mod x^{s^{d'}} - x$$d' \leq d$

Myślę, że jest na to dość szybki sposób. Niech współczynniki jeszcze nieznanego wielomianu będą , więc gdzie jest jakąś małą liczbą. Teraz zacznijmy obliczać gdzie , gdzie jest duże, a są znane. Robimy to poprzez zmniejszenie stopnia przy użyciu równości jako . Ostatecznie otrzymujemy wielomian stopnia , którego współczynniki są wielomianami (ponieważ$q$$b_i$$q=\sum_{i=0}^d b_ix^i$$d$$p \pmod q$$p=\sum_{i=0}^D a_ix^i$$D$$a_i$$a_Dx^D= \frac {-a_D}{b_d} \sum_{i=1}^{d-1} b_{d-i}x^{D-i}$$<d-1$$b_i$$a_i$są znane). Te wielomiany możemy szybko obliczyć po otrzymaniu .$q$

Zobacz doskonałe komentarze na temat tego postu poniżej. :)

Przetwarzanie wstępne; wejście: $p(x)$

1. Współczynnik jako .$p(x)$$p(x)=\prod_{i=0}^{1000} (x_i-r_i)$

2. Przechowuj to jako tabelę różnych pierwiastków i ich odpowiednich krotności .$T$$r_j$$m_j$

Faza online; wejście: $q(x)$

1. Współczynnik jako .$q(x)$$q(x)=\prod_{i=0}^5 (x_i-r'_i)$

2. Przechowuj to jako listę różnych pierwiastków i ich odpowiednich krotności .$L$$r'_j$$m'_j$

3. Podczas gdy nie jest pusta, usunąć następnego głównego / wielość z i jakiekolwiek podobne określenia w .$L$$L$$T$

4. Odczytaj ze zmodyfikowanej tabeli i .$p(x)\bmod{q(x)}$$T$

Inne komentarze:

• Oczywiście chcesz posortować tabelę i uzyskać do niej dostęp za pomocą wyszukiwania binarnego (lub drzewa).$T$
• (Niech będzie stopniem .) Jeśli chcesz, aby wynik był w reprezentacji współczynnika, możesz po prostu wykonać kilka FFT na końcu, aby uzyskać .$d$$p(x)$$p(x)\bmod{q(x)}$$\tilde{O}(d)$
• W zależności od tego, jak go sformalizujesz, prawdopodobnie prawdopodobnie wcześniej obliczysz wiele różnych sposobów rekombinacji terminów w (dynamiczny styl programowania), tak że większość (lub wszystkie) mnożenia to tylko wyszukiwania. Dominującym kosztem jest wtedy liczba wyszukiwań lub w przybliżeniu . Jeśli , jest to tylko garść konkretnych operacji arytmetycznych.$T$$O(\log d)$$d=1000$