Akar bilangan bulat dari suatu polinomial

10

Algoritma apa yang dapat kita gunakan untuk menemukan semua akar bilangan bulat dari polinomial dengan koefisien bilangan bulat?f(x)

Saya mengamati bahwa Sage dapat menemukan akar dalam beberapa detik bahkan ketika semua koefisien sangat besar. Bagaimana itu bisa dilakukan?f(x)

ds.algorithms na.numerical-analysis pengguna12290
sumber
1
Apakah Anda mencari algoritme untuk mengembalikan akar integer dari polinomial yang diberikan? Jika ya, itu tidak dapat dipastikan dan pertanyaannya di luar topik di sini. Anda bisa menanyakannya pada Ilmu Komputer yang memiliki cakupan lebih luas.
Kaveh
7
Tahan. Mengapa tidak diputuskan membuat pertanyaan di luar topik? Ini adalah pertanyaan tingkat penelitian yang sah.
Jeffε
2
Jadi, bagaimana Sage melakukannya? Tidak dapat diputuskan — bahkan diketahui tidak dapat diputuskan — tidak membuat masalah secara teoritis tidak menarik. Ilmuwan komputer teoretis menyelesaikan masalah yang tidak dapat dipastikan sepanjang waktu - lihat, misalnya, semua verifikasi berbantuan komputer.
Jeffε
11
Kaveh, apa yang Anda katakan itu tidak benar. Apa yang tidak dapat diputuskan adalah solvabilitas persamaan Diophantine dengan banyak variabel (sehingga ada banyak solusi nyata tanpa batas dan satu mencari integer / rasional). Tetapi pertanyaan ini adalah tentang polinomial un-variate , yang tentu saja dapat didekati (jika f ( x ) adalah derajat d , ada hingga d akar dan satu dapat memeriksa mana yang merupakan bilangan bulat). f(x)f(x)dd
Mahdi Cheraghchi
1
@Pratik Anda tidak perlu pangkalan Gröbner dalam kasus univariat.
Yuval Filmus

Jawaban:

10

Dengan asumsi bahwa koefisien adalah bilangan bulat atau rasional dan Anda ingin akar bilangan bulat, pendekatan paling sederhana adalah dengan menggunakan bilangan bulat atau teorema akar rasional. Lihat http://en.wikipedia.org/wiki/Rational_root_theorem Seperti dicatat oleh DW, ini mungkin bermasalah jika koefisien konstan sulit untuk faktor (lihat juga /math/123018/polynomial- dan-integer-root )f

Bagaimanapun, dokumentasi Sage dengan jelas menjelaskan bagaimana mereka melakukan pencarian root: "Metode selanjutnya, yang digunakan jika K adalah domain integral, adalah mencoba memfaktorkan polinomial. Jika ini berhasil, maka untuk setiap gelar-satu faktor a * x + b, kita tambahkan -b / a sebagai root (selama hasil bagi ini sebenarnya di ring yang diinginkan). " Lihat http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html .

Jadi pertanyaan Anda menjadi Bagaimana mereka faktor faktor polinomial dengan koefisien integer? Rupanya, Sage memanggil NTL untuk melakukan itu (lihat http://www.shoup.net/ntl/doc/ZZXFactoring.txt untuk detail NTL).

Jika Anda menginginkan metode efisien asimptotik, Anda bisa merujuk ke metode Lenstra, Lenstra, dan Lovasz ( https://openaccess.leidenuniv.nl/handle/1887/3810 ).

minar
sumber
1
Terima kasih atas bantuannya! Menarik. Mungkinkah Anda bersedia mengedit jawaban Anda untuk menguraikan cara mengubahnya menjadi suatu algoritma, dan berapa waktu berjalannya? Apakah waktu berjalan yang terburuk bersifat eksponensial (karena dapat mengambil waktu subeksponensial menjadi faktor, dan kemudian mungkin ada banyak pembagi secara eksponensial dari koefisien terkemuka dan tertinggal)? Jika ya, apakah ada algoritma yang lebih baik, atau ini tentang yang terbaik yang bisa dilakukan? Juga, bukankah pendekatan ini hanya menemukan akar rasional, tetapi bukan akar irasional?
DW
Membaca ulang pertanyaan dan melihat bahwa Anda menafsirkannya secara berbeda, saya tidak lagi sepenuhnya yakin, tetapi bagi saya dan beberapa komentator tampak jelas bahwa pertanyaan itu menanyakan tentang akar bilangan bulat. Tidakkah kamu membacanya seperti itu?
minar
@ minar, kamu benar. Sekarang saya membaca kembali pertanyaannya, sepertinya memang begitu. Saya harus membaca pertanyaan itu terlalu cepat. (Awalnya saya salah mengartikan pertanyaan itu sebagai menyiratkan bahwa kami ingin semua akar polinom dengan koefisien bilangan bulat, tetapi saat membaca kembali pertanyaan itu, yang sepertinya seperti salah tafsir.)
DW
2
Untuk metode yang asimptot dan praktis , algoritma yang paling terkenal adalah dengan van Hoeij (lihat di sini ). Sebenarnya, NTL tampaknya menggunakannya.
Bruno