Anjak polinomial tingkat rendah

8

Apa algoritma tercepat yang dikenal untuk memfaktorkan polinomial dengan variabel dan derajat total d ? Di sini, n tumbuh dan d diperbaiki. Sebagian besar pekerjaan tampaknya mempertimbangkan kasus ketika d tumbuh dan n diperbaiki. Saya tertarik pada hasil, baik di bidang terbatas maupun rasional.ndnddn

arnab
sumber

Jawaban:

8

Biarkan menjadi bidang karakteristik 0 atau setidaknya d ( d - 1 ) + 1 , dan p K [ x 1 , , x n ] menjadi polinomial total derajat paling banyak d . Jika d adalah tetap dan n bertambah, seseorang memiliki kompleksitas sebagai berikut untuk pengurangan faktorisasi p ke faktorisasi derajat -d polinomial univariat: (Notasi ˜ O ( )K0d(d1)+1pK[x1,,xn]ddnpdO~() mengabaikan faktor logaritmik.)

  1. Algoritme deterministik:

    • O~((n+dn)4)
    • O~((n+2d2n1)dω)2<ω3
  2. Algoritma probabilitas:

    • O~((n+dn)) operasi lapangan, jika algoritma multiplikasi cepat tersedia.

Kemudian, kita harus pd sebuah univariat degree- polinomial. Kompleksitas langkah ini tidak bergantung pada lagi, sehingga batas di atas tetap valid untuk algoritma faktorisasi lengkap. Satu-satunya perbedaan adalah dalam karakteristik positif: Karena tidak ada algoritma waktu polinomial deterministik diketahui faktor polinomial univariat, bahkan pengurangan deterministik menghasilkan algoritma probabilistik. Meskipun demikian, jika benar-benar tetap dan kecil, seseorang dapat mengganti algoritma polinomial-waktu probabilistik dengan yang waktu-eksponensial deterministik.n ddnd

Perhatikan bahwa batas probabilistik optimal hingga faktor logaritmik karena adalah ukuran dari memasukkan.(n+dO~((n+dn))(n+dn)

Rincian lebih lanjut dapat ditemukan dalam makalah Algoritma faktorisasi polinomial polinomial multivariat padat yang ditingkatkan dari Grégoire Lecerf ( tautan tanpa paywall ).

Referensi lain, terutama untuk bidang dengan karakteristik kecil, adalah EL Kaltofen & G. Lecerf, Faktorisasi polinomial multivariat ( tautan tanpa paywall ), bab 11.5 dari GL Mullen dan D. Panario, editor, Handbook of the finite field .

¹ Hasilnya perlu mengasumsikan bahwa .ω>2

Bruno
sumber
Terimakasih banyak! Apakah Anda tahu tentang pekerjaan di bidang yang sangat kecil, katakanlah GF (2)?
arnab
3
Batasan yang saya sebutkan dalam jawaban saya diberikan oleh algoritma yang mengurangi faktorisasi multivarian menjadi faktorisasi univariat. AFAIK, batas paling dikenal ketika hasil di atas tidak berlaku (yaitu ketika karakteristik terlalu kecil) diberikan oleh algoritma yang melakukan pengurangan multivariat → bivariat → univariat. Untuk lebih lanjut tentang ini, Anda dapat melihat Factorisasi polinomial multivariat oleh Kaltofen dan Lecerf, bab 11.5 dari Buku Pegangan bidang terbatas . Versi awal bab ini ada di sini .
Bruno