Liczby całkowite wielomianu

10

Jakiego algorytmu możemy użyć do znalezienia wszystkich pierwiastków całkowitych wielomianu o współczynnikach całkowitych?f(x)

Zauważyłem, że Sage może znaleźć pierwiastki w ciągu kilku sekund, nawet jeśli wszystkie współczynniki są bardzo duże. Jak to zrobić?f(x)

ds.algorithms na.numerical-analysis użytkownik12290
źródło
1
Czy szukasz algorytmu do zwracania liczby całkowitej pierwiastka z danego wielomianu? Jeśli tak, to jest nierozstrzygalne, a pytanie jest tutaj nie na temat. Możesz o to zapytać w informatyce, która ma szerszy zakres.
Kaveh
7
Czekaj. Dlaczego niezdecydowanie sprawia, że ​​pytanie jest nie na temat? To uzasadnione pytanie na poziomie badawczym.
Jeffε
2
Jak więc Sage to robi? Bycie nierozstrzygalnym - a nawet bycie znanym jako nierozstrzygalnym - nie czyni problemu teoretycznie nieciekawym. Informatycy teoretyczni cały czas rozwiązują nierozstrzygalne problemy - patrz na przykład cała weryfikacja wspomagana komputerowo.
Jeffε
11
f(x)f(x)dd
1
@Pratik Nie potrzebujesz baz Gröbnera w przypadku jednego wariantu.
Yuval Filmus,

Odpowiedzi:

10

f

W każdym razie dokumentacja Sage jasno wyjaśnia, w jaki sposób przeprowadzają wyszukiwanie roota: „Następną metodą, która jest używana, jeśli K jest domeną integralną, jest próba uwzględnienia wielomianu. Jeśli to się powiedzie, to dla każdego stopnia pierwszego współczynnik a * x + b, dodajemy -b / a jako pierwiastek (o ile ten iloraz faktycznie znajduje się w żądanym pierścieniu). ” Zobacz http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html .

Twoje pytanie brzmi: w jaki sposób efektywnie uwzględniają wielomiany ze współczynnikami całkowitymi? Najwyraźniej Sage dzwoni do NTL, aby to zrobić ( szczegółowe informacje na temat NTL można znaleźć na stronie http://www.shoup.net/ntl/doc/ZZXFactoring.txt ).

Jeśli chcesz asymptotycznie wydajnej metody, możesz odnieść się do metody Lenstry, Lenstry i Lovasz ( https://openaccess.leidenuniv.nl/handle/1887/3810 ).

minar
źródło
1
Dzięki za pomocną wskazówkę! Fascynujący. Czy możesz zechcieć edytować swoją odpowiedź, aby opracować sposób przekształcenia tego w algorytm i jaki jest jego czas działania? Czy najgorszy przypadek czasu działania ma charakter wykładniczy (ponieważ uwzględnienie czynnika może zająć czas podwykonawczy, a następnie może być wykładniczo wiele dzielników współczynnika wiodącego i końcowego)? Jeśli tak, to czy istnieją lepsze algorytmy, czy jest to najlepsze, co można zrobić? Ponadto, czy to podejście nie znajduje tylko racjonalnych korzeni, ale nie irracjonalnych korzeni?
DW
Ponownie czytając pytanie i widząc, że interpretujesz je inaczej, nie jestem już całkowicie pewien, ale dla mnie i niektórych komentatorów wydawało się jasne, że pytanie dotyczy korzeni całkowitych. Nie czytasz tego w ten sposób?
minar
@minar, masz rację. Teraz, gdy ponownie przeczytałem pytanie, wydaje się, że tak jest. Musiałem zbyt szybko przeczytać pytanie. (Początkowo błędnie zinterpretowałem pytanie jako sugerujące, że chcemy wszystkich pierwiastków wielomianu ze współczynnikami całkowitymi, ale po ponownym odczytaniu pytania wydaje się to błędną interpretacją.)
DW
2
W przypadku asymptotycznie i praktycznie wydajnej metody najbardziej znanym algorytmem jest van Hoeij (patrz tutaj ). Właściwie wydaje się, że używa go NTL.
Bruno,