Ich suche nach einem schnellen Algorithmus, um die Wurzeln eines univariaten Polynoms in einem primitiven endlichen Feld zu finden.
Das heißt, wenn f = a0 + a1x + a2x2 + ... + anxn (n & gt; 0) dann ein Algorithmus, der für eine gegebene Primzahl p alle r < p befriedigend f(r) = 0 mod p findet.
Ich fand Chiens Suchalgorithmus Ссылка , aber ich kann mir nicht vorstellen, dass dies für Primzahlen größer als 20 Bit so schnell ist. Hat jemand Erfahrung mit Chiens Suchalgorithmus oder kennt man einen schnelleren Weg? Gibt es ein sympy Modul dafür?
Dies ist ziemlich gut untersucht, wie mcdowellas Kommentar zeigt. So funktioniert der Zufallsalgorithmus Cantor-Zassenhaus für den Fall, dass Sie die Wurzeln finden wollen eines Polynoms statt der allgemeineren Faktorisierung.
Beachten Sie, dass im Ring von Polynomen mit Koeffizienten mod p das Produkt x (x-1) (x-2) ... (x-p + 1) alle möglichen Wurzeln hat und gleich x ^ px by
Wegen der speziellen Form von x ^ px mit nur zwei von Null verschiedenen Termen kann der erste Schritt des Euklid-Algorithmus durch wiederholt werden Quadrierung , in etwa 2 log_2 (p) Schritten, die nur Polynome mit einem Grad von nicht mehr als dem doppelten Grad von f beinhalten, mit Koeffizienten mod p. Wir können x mod f, x ^ 2 mod f, x ^ 4 mod f usw. berechnen, dann die Terme, die Nichtnullstellen in der binären Expansion von p entsprechen, zusammen multiplizieren, um x ^ p mod f zu berechnen und schließlich x subtrahieren.
Wiederhole das Folgende: Wähle ein zufälliges d in Z / p. Berechnen Sie die GCD von g mit r_d = (x + d) ^ ((p-1) / 2) -1, was wir wiederum schnell mit dem Euklid-Algorithmus berechnen können, indem wir im ersten Schritt die Quadrierung wiederholen. Wenn der Grad dieser GCD genau zwischen 0 und dem Grad von g liegt, haben wir einen nichttrivialen Faktor von g gefunden, und wir können rekapitulieren, bis wir die linearen Faktoren, also Wurzeln von g und somit f gefunden haben.
Wie oft funktioniert das? r_d hat als Wurzeln die Zahlen, die d kleiner sind als ein von Null verschiedenes Quadrat mod p. Betrachte zwei verschiedene Wurzeln von g, a und b, also sind (x-a) und (x-b) Faktoren von g. Wenn a + d ein Quadrat ungleich Null ist und b + d nicht, dann ist (xa) ein gemeinsamer Faktor von g und r_d, während (xb) nicht ist, was bedeutet, dass GCD (g, r_d) ein nichttrivialer Faktor von g ist . Ähnlich ist, wenn b + d ein von Null verschiedenes Quadrat ist, während a + d nicht ist, dann (x-b) ein gemeinsamer Faktor von g und r_d, während (x-a) nicht ist. Nach der Zahlentheorie kommt der eine oder der andere Fall nahe der Hälfte der möglichen Auswahlmöglichkeiten für d vor, was bedeutet, dass es im Durchschnitt eine konstante Anzahl von Möglichkeiten von d braucht, bevor wir einen nichttrivialen Faktor von g finden, nämlich einen trennenden (xa) von (xb).
Ihre Antworten sind gut, aber ich denke, ich fand eine wunderbare Methode, um die Wurzeln modulo irgendeine Zahl zu finden: Diese Methode basiert auf "LATTICES". Sei r R eine Wurzel von mod p . Wir müssen eine andere Funktion wie h (x) finden, so dass h nicht groß ist und r Wurzel von h . Gittermethode finde diese Funktion. Beim ersten Mal müssen wir eine Basis für das Polynom für das Gitter erstellen, und dann finden wir mit dem "LLL" -Algorithmus einen "kürzesten Vektor", der Wurzel r ohne modulo p . Auf diese Weise eliminieren wir modulo p .
Für weitere Erklärungen, siehe "Kupferschmied D. Finden kleiner Lösungen für Polynome kleinen Grades. In Kryptographie und Gitter".
Tags und Links algorithm sympy polynomial-math polynomials