Faktor eines Polynoms über ein endliches Feld oder die ganzen Zahlen

20

Zerlegen Sie ein Polynom ohne Verwendung integrierter Factoring- / Polynomfunktionen vollständig in irreduzible Zahlen über die ganzen Zahlen oder ein endliches Feld.

Eingang

Ihr Programm / Ihre Funktion erhält eine Primzahl (oder Null) nals Eingabe. Das Feld / Ring ist das finite Feld dieser Reihenfolge (dh Z/nZ), oder einfach nur , Zwenn nist 0. Ihr Programm kann fehlschlagen, wenn nes nicht 0oder eine Primzahl ist. Das Polynom wird in sein F[x].

Ihr Programm / Ihre Funktion erhält auch das Polynom als Eingabe.

Die Eingabe ist flexibel. Geben Sie unbedingt an, wie Sie Eingaben erhalten möchten. Zum Beispiel könnte das Polynom als eine Liste von Koeffizienten oder in der Form eingegeben werden, die die meisten Leute erwarten (z. B. 50x^3 + x^2), oder in einer anderen vernünftigen Form. Oder das Format der Eingabe des Feldes / Rings kann auch unterschiedlich sein.

Ausgabe

Ihr Programm / Ihre Funktion gibt das vollständig faktorisierte Polynom aus. Sie können mehrere Wurzeln erweitert lassen (dh (x + 1)(x + 1)anstelle von (x + 1)^2). Sie können Leerzeichen zwischen Binäroperatoren entfernen. Sie können die Gegenüberstellung durch ersetzen *. Sie können an seltsamen Stellen Leerzeichen einfügen. Sie können die Faktoren in beliebiger Reihenfolge neu anordnen. Der xBegriff könnte einfach sein (x). xkann geschrieben werden als x^1; Der konstante Term kann jedoch nicht haben x^0. Fremdzeichen +sind zulässig. Möglicherweise haben Sie keine Klausel mit einem 0vorne, sie müssen weggelassen werden. Der führende Term jedes Faktors muss positiv sein, negative Vorzeichen müssen außerhalb liegen.

In Testfällen sollte Ihr Programm in der Lage sein, in angemessener Zeit (z. B. <= 2 Stunden) für jeden dieser Fälle eine Ausgabe zu erstellen:

Eingang: 2, x^3 + x^2 + x + 1

Ausgabe: (x + 1)^3

Eingang: 0, x^3 + x^2 + x + 1

Ausgabe: (x + 1)(x^2 + 1)

Eingang: 0, 6x^4 – 11x^3 + 8x^2 – 33x – 30

Ausgabe: (3x + 2)(2x - 5)(x^2 + 3)

Eingang: 5, x^4 + 4x^3 + 4x^2 + x

Ausgabe: x(x + 4)(x + 4)(x + 1)

Eingang: 0, x^5 + 5x^3 + x^2 + 4x + 1

Ausgabe: (x^3 + 4x + 1)(x^2 + 1)

Besonderer Dank geht an Peter Taylor für die Kritik meiner Testfälle

Justin
quelle
1
Ich denke, das gibt mir einen Rückblick auf einige der schwierigeren Mathematikstudenten . Gehe ich hier überhaupt in die richtige Richtung?
Digital Trauma
1
Dies erinnert mich an die Zeit, als ich Albträume hatte, die versuchten, Polynome korrekt zu drucken ...
Sp3000
Entschuldigung, dass ich nicht verstanden habe, aber was soll die erste eingegebene Nummer tun? oder wie wirkt es sich auf die ausgabe aus?
Optimierer
@Optimizer Die erste Eingabenummer bestimmt, über welches Feld / welche Ganzzahlen Sie arbeiten. Wenn die Zahl ungleich Null ist, bearbeiten Sie das endliche Feld dieser Reihenfolge. Ein endliches Ordnungsfeld phat die Elemente {0, 1, ... , p-1}und befindet sich unter Addition / Multiplikation mod p. Reduziere im Grunde genommen jeden Koeffizienten um Mod pund du bist gut. Beachten Sie auch, dass , wenn es eine Wurzel hat, dh linearen Faktor, von {0, ... , p-1}produzieren 0(mod p) , wenn es in das Polynom gesteckt.
Justin
1
@flawr, der Standardansatz für das Factoring Zbesteht darin, Z/pZeinen geeigneten pund dann Hensel-Lift zu berücksichtigen . Der golffähige Ansatz ist jedoch wahrscheinlich (und dies ist sicherlich der Weg, den ich betrachte), eine einfache Grenze für die Höhe der Faktoren zu verwenden und sie brutal zu erzwingen.
Peter Taylor

Antworten:

17

GolfScript (222 Bytes)

~.@:[email protected]\{abs+}/2@,2/)?*or:^{\1$^base{^q- 2/-}%.0=1=1$0=q>+{{:D[1$.,2$,-)0:e;{.0=0D=%e|:e;(D(@\/:x@@[{x*~)}%\]zip{{+}*q!!{q%}*}%}*e+])0-{;0}{@;@\D.}if}do}*;\).^3$,)2/?<}do;][[1]]-{'('\.,:x;{.`'+'\+'x^'x(:x+x!!*+\!!*}%')'}/

Online-Demo

Anmerkungen

  1. Auf das Eingabeformat nfolgt ein GolfScript-Array mit Koeffizienten von den höchsten bis zu den niedrigsten Werten. ZB 0, x^5 + 5x^3 + x^2 + 4x + 1sollte formatiert sein als 0 [1 0 5 1 4 1].
  2. Über ein endliches Feld gibt es nur endlich viele Polynome, die so klein sind, dass sie relevant sind. Dies ist jedoch nicht der Fall Z. Ich Zgehe damit um, indem ich eine entspannte Form von Mignottes Höhenband benutze. Eine großartige Abhandlung über Größenbeschränkungen beim Factoring ist Bounds on Factors in Z [x] , John Abbott, 2009 (Link ist zum Vorabdruck von arxiv; sein Lebenslauf besagt, dass er vom Journal of Symbolic Computation akzeptiert wurde ). Die entspannteste Form gibt es in Bezug auf die L-2-Norm, aber um Bytes zu sparen, entspanne ich mich weiter und verwende stattdessen die L-1-Norm. Dann ist es ein Fall von Brute Forcing durch Prozessabteilung.
  3. Über ein endliches Feld ist jedes Polynom eine Konstante mal ein monisches Polynom, also teile ich nur durch monische Polynome und speichere ein Reziprok im Feld. Es Zist jedoch nur ein Ring und daher ist es notwendig, eine Testdivision durch nicht-monische Kandidatenfaktoren durchzuführen. Es gelingt mir, keine rationalen Zahlen zu implementieren, indem ich einen Leitfaktor-Divisionstest durchführe und ein "Fehler" -Flag anhäufe e.
  4. Beide Punkte 2 und 3 implizieren, dass der Fall des Factorings im ZAllgemeinen langsamer ist und nicht mit der Online-Demo getestet werden kann. Der langsamste der offiziellen Testfälle dauert jedoch 10 Minuten, was deutlich innerhalb des "angemessenen" Zeitlimits liegt.
Peter Taylor
quelle