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

9

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?

paulwaters
źródło

Odpowiedzi:

3

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 re. Następnie modq, wiemy xsre=xtrzyma. Dlatego wystarczy wstępnie obliczyć .p(x)modxsre-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=q1qrpq1,,qrp(x)modxsre-xrere

David Harris
źródło
2

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żqbjaq=ja=0rebjaxjarep(modq)p=ja=0rezajaxjarezajazarexre=-zarebreja=1re-1bre-jaxre-ja<re-1bjazajasą znane). Te wielomiany możemy szybko obliczyć po otrzymaniu .q

domotorp
źródło
-1

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)=ja=01000(xja-rja)

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

Faza online; wejście: q(x)

  1. Współczynnik jako .q(x)q(x)=ja=05(xja-rja)

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

  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)modq(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ć .rep(x)p(x)modq(x)O~(re)
  • 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(logre)re=1000
Daniel Apon
źródło
2
W jakim polu faktorujesz p? Jak duża powinna być reprezentacja w stosunku do pierwotnego pola? A kiedy mówisz, że chcesz odczytać ze zmodyfikowanej tabeli i danych wyjściowych, co masz na myśli?
David Eppstein
2
Działa to tylko wtedy, gdy działasz na polu, na którym rozdzielone są zarówno jak i . Ale wydaje się to zależeć od ; w szczególności nie można wstępnie obliczyć pierwiastków dla samego . Ponadto obliczenie pierwiastków na tak dużym polu zajmie trochę czasu (przynajmniej); nie jest to lepsze niż naiwny algorytm. pqqpq|p|
David Harris