Ganzzahlige Wurzeln eines Polynoms

10

Welchen Algorithmus können wir verwenden, um alle ganzzahligen Wurzeln eines Polynoms mit ganzzahligen Koeffizienten zu finden?f(x)

Ich beobachte, dass Sage die Wurzeln innerhalb weniger Sekunden finden kann, selbst wenn alle Koeffizienten von sehr groß sind. Wie ist das möglich?f(x)

ds.algorithms na.numerical-analysis user12290
quelle
1
Suchen Sie nach einem Algorithmus, der eine ganzzahlige Wurzel eines bestimmten Polynoms zurückgibt? Wenn ja, ist das unentscheidbar und die Frage ist hier nicht zum Thema. Sie können es in der Informatik fragen, die einen breiteren Anwendungsbereich hat.
Kaveh
7
Warten Sie mal. Warum macht Unentscheidbarkeit die Frage nicht zum Thema? Dies ist eine legitime Frage auf Forschungsebene.
Jeffs
2
Also, wie macht Sage das? Unentscheidbar zu sein - selbst wenn man bekanntermaßen unentscheidbar ist - macht das Problem theoretisch nicht uninteressant. Theoretische Informatiker lösen ständig unentscheidbare Probleme - siehe zum Beispiel die gesamte computergestützte Überprüfung.
Jeffs
11
f(x)f(x)dd
1
@Pratik Im univariaten Fall brauchst du keine Gröbner-Basen.
Yuval Filmus

Antworten:

10

f

In jedem Fall erklärt die Sage-Dokumentation deutlich, wie sie die Wurzelsuche durchführen: "Die nächste Methode, die verwendet wird, wenn K eine integrale Domäne ist, besteht darin, zu versuchen, das Polynom zu faktorisieren. Wenn dies erfolgreich ist, dann für jeden Grad eins Faktor a * x + b addieren wir -b / a als Wurzel (solange sich dieser Quotient tatsächlich im gewünschten Ring befindet). " Siehe http://www.sagemath.org/doc/reference/polynomial_rings/sage/rings/polynomial/polynomial_element.html .

Ihre Frage lautet also: Wie faktorisieren sie Polynome effizient mit ganzzahligen Koeffizienten? Anscheinend ruft Sage NTL an, um dies zu tun ( Einzelheiten zu NTL finden Sie unter http://www.shoup.net/ntl/doc/ZZXFactoring.txt ).

Wenn Sie eine asymptotisch effiziente Methode wünschen, können Sie sich auf die Methode von Lenstra, Lenstra und Lovasz beziehen ( https://openaccess.leidenuniv.nl/handle/1887/3810 ).

Minar
quelle
1
Danke für den hilfreichen Hinweis! Faszinierend. Könnten Sie bereit sein, Ihre Antwort zu bearbeiten, um herauszufinden, wie dies in einen Algorithmus umgewandelt werden kann und wie die Laufzeit ist? Ist die Laufzeit im ungünstigsten Fall exponentiell (weil das Faktorisieren subexponentielle Zeit in Anspruch nehmen kann und es dann möglicherweise exponentiell viele Teiler des führenden und nachfolgenden Koeffizienten gibt)? Wenn ja, gibt es bessere Algorithmen oder ist dies das Beste, was man tun kann? Findet dieser Ansatz nicht auch nur die rationalen Wurzeln, aber nicht die irrationalen Wurzeln?
DW
Wenn ich die Frage noch einmal lese und sehe, dass Sie sie anders interpretieren, bin ich mir nicht mehr ganz sicher, aber mir und einigen Kommentatoren schien klar zu sein, dass die Frage nach ganzzahligen Wurzeln fragt. Lesen Sie es nicht so?
Minar
@minar, du hast recht. Jetzt, wo ich die Frage noch einmal gelesen habe, scheint es so. Ich muss die Frage zu schnell gelesen haben. (Ich habe die Frage anfangs falsch interpretiert, was bedeutet, dass wir alle Wurzeln eines Polynoms mit ganzzahligen Koeffizienten wollen, aber beim erneuten Lesen der Frage scheint dies eine Fehlinterpretation zu sein.)
DW
2
Für eine asymptotisch und praktisch effiziente Methode ist der bekannteste Algorithmus von van Hoeij (siehe hier ). Eigentlich scheint NTL es zu benutzen.
Bruno