Temukan sisa polinomial tetap besar ketika dibagi dengan polinomial kecil yang tidak diketahui

Asumsikan kita beroperasi di bidang yang terbatas. Kami diberi p polinomial tetap besar (x) (dari, katakanlah, derajat 1000) di atas bidang ini. Polinomial ini diketahui sebelumnya dan kami diizinkan untuk melakukan perhitungan menggunakan banyak sumber daya dalam "tahap awal." Hasil ini dapat disimpan dalam tabel pencarian yang cukup kecil.

Pada akhir "fase awal", kita akan diberi sedikit polinomial q (x) (dari, katakanlah, derajat 5 atau kurang).

Apakah ada cara cepat untuk menghitung p (x) mod q (x) mengingat kita diizinkan untuk melakukan beberapa perhitungan rumit dalam "fase awal"? Salah satu cara yang jelas adalah menghitung p (x) mod q (x) untuk semua nilai yang mungkin dari q (x). Apakah ada cara yang lebih baik untuk melakukan ini?

Algoritma berikut bekerja dengan baik jika bidang yang mendasari memiliki urutan yang sangat kecil .$s$

Misalkan kita tahu tidak dapat direduksi, dengan tingkat yang tetap . Kemudian, mod , kita tahu tahan. Karena itu cukup untuk melakukan pre-compute .d q x s d = x p ( x $q$$d$$q$$x^{s^d} = x$$p(x) \mod x^{s^d} - x$

Secara umum, dapat terurai menjadi produk dari polinomial yang tidak dapat direduksi. . Dalam hal ini, argumen yang sama berlaku untuk komputasi Modulo setiap secara terpisah, dan kemudian piecing hasil bersama-sama. Jadi kita benar-benar perlu menghitung untuk setiap .$q(x)$ p q 1 , ... , q r p ( x $q = q_1 \dots q_r$$p$$q_1, \dots, q_r$d ′ ≤ $p(x) \mod x^{s^{d'}} - x$$d' \leq d$

Saya pikir ada cara yang cukup cepat untuk melakukan ini. Biarkan koefisien dari polinomial belum diketahui menjadi , jadi mana adalah sejumlah kecil. Sekarang mari kita mulai menghitung mana , di mana besar dan diketahui. Ini kita lakukan dengan mengurangi derajat menggunakan persamaan sebagai . Akhirnya yang kita dapatkan adalah derajat polinomial, yang koefisiennya adalah polinomial dari (karenab i q = Σ d i = 0 b i x i d $q$$b_i$$q=\sum_{i=0}^d b_ix^i$$d$p = ∑ D i = 0 a i x i D a i a D x D = - a $p \pmod q$$p=\sum_{i=0}^D a_ix^i$$D$$a_i$<d-1biai$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$dikenal). Polinomial ini dapat kita hitung dengan cepat begitu kita mendapatkan .$q$

Lihat komentar luar biasa tentang pos ini di bawah. :)

Preprocessing; input: $p(x)$

1. Faktor sebagai .p ( x ) = ∏ 1000 i = 0 ( x i - r i$p(x)$$p(x)=\prod_{i=0}^{1000} (x_i-r_i)$

2. Simpan ini sebagai tabel dari akar yang berbeda dan multiplisitas masing-masing .r j m $T$$r_j$$m_j$

Fase online; input: $q(x)$

1. Faktor sebagai .q ( x ) = ∏ 5 i = 0 ( x i - r ′ i$q(x)$$q(x)=\prod_{i=0}^5 (x_i-r'_i)$

2. Simpan ini sebagai daftar dari akar yang berbeda dan multiplisitas masing-masing .r ′ j m ′ $L$$r'_j$$m'_j$

3. Sementara tidak kosong, menghapus berikutnya root / multiplisitas dari dan setiap seperti istilah dalam .L $L$$L$$T$

4. Baca dari tabel dan output yang dimodifikasi .$p(x)\bmod{q(x)}$$T$

Komentar lain:

• Jelas Anda ingin mengurutkan tabel dan mengaksesnya dengan pencarian biner (atau pohon).$T$
• (Misalkan menjadi derajat .) Jika Anda ingin output berada dalam representasi koefisien, Anda bisa melakukan banyak FFT pada akhirnya untuk mendapatkan waktu.p ( x ) p ( x ) mod q ( x ) ˜ O ( d $d$$p(x)$$p(x)\bmod{q(x)}$$\tilde{O}(d)$
• Bergantung pada bagaimana Anda memformalkannya, Anda mungkin dapat melakukan pra-komputasi banyak berbagai cara Anda akan mengkombinasikan kembali istilah dalam sebelumnya (gaya pemrograman dinamis), sehingga sebagian besar (atau semua) dari perkalian hanyalah pencarian. Biaya yang mendominasi adalah jumlah pencarian, atau kira-kira . Jika , ini hanya sedikit operasi aritmatika yang konkret.O ( log d ) d = $T$$O(\log d)$$d=1000$