Finden Sie den Rest eines großen festen Polynoms, wenn es durch ein kleines unbekanntes Polynom geteilt wird

9

Angenommen, wir arbeiten in einem endlichen Feld. Über diesem Feld erhalten wir ein großes festes Polynom p (x) (von beispielsweise Grad 1000). Dieses Polynom ist im Voraus bekannt und wir dürfen in der "Anfangsphase" mit vielen Ressourcen rechnen. Diese Ergebnisse können in relativ kleinen Nachschlagetabellen gespeichert werden.

Am Ende der "Anfangsphase" erhalten wir ein kleines unbekanntes Polynom q (x) (von beispielsweise Grad 5 oder weniger).

Gibt es eine schnelle Möglichkeit, p (x) mod q (x) zu berechnen, da wir in der "Anfangsphase" einige komplizierte Berechnungen durchführen dürfen? Ein naheliegender Weg besteht darin, p (x) mod q (x) für alle möglichen Werte von q (x) zu berechnen. Gibt es einen besseren Weg, dies zu tun?

Paulwaters
quelle

Antworten:

3

Die folgenden Algorithmen funktionieren gut , wenn das zugrunde liegende Feld einen sehr kleinen Auftrag hat .s

Nehmen wir an, wir wissen, dass irreduzibel ist und einen festen Grad . Dann, mod , wissen wir, dass gilt. Daher reicht es aus, vorab zu berechnen .d q x s d = x p ( x )qdqxsd=xp(x)modxsdx

Im Allgemeinen kann sich in ein Produkt irreduzibler Polynome zerlegen . In diesem Fall gilt ein ähnliches Argument für die Berechnung von modulo für jedes separat und das anschließende Zusammensetzen der Ergebnisse. Wir müssen also wirklich für jedes berechnen .q = q 1q r p q 1 , , q r p ( x )q(x)q=q1qrpq1,,qrd 'dp(x)modxsdxdd

David Harris
quelle
2

Ich denke, es gibt einen ziemlich schnellen Weg, dies zu tun. Die Koeffizienten des noch unbekannten Polynoms seien , also wobei eine kleine Zahl ist. Beginnen wir nun mit der Berechnung von wobei , wobei groß ist und bekannt sind. Dazu reduzieren wir den Grad unter Verwendung von Gleichungen wie . Schließlich erhalten wir ein Polynom vom Grad , dessen Koeffizienten Polynome des (seit demb i q = d i = 0 b i x i d pqbiq=i=0dbixidp = D i = 0 a i x i D a i a D x D = - a D.p(modq)p=i=0DaixiDai<d-1biaiqaDxD=aDbdi=1d1bdixDi<d1biaisind bekannt). Diese Polynome können wir schnell berechnen, sobald wir .q

domotorp
quelle
-1

Siehe ausgezeichnete Kommentare zu diesem Beitrag unten. :) :)


Vorverarbeitung; Eingabe: p(x)

  1. Faktor als .p ( x ) = 1000 i = 0 ( x i - r i )p(x)p(x)=i=01000(xiri)

  2. Speichern Sie dies als Tabelle verschiedener Wurzeln und ihrer jeweiligen Multiplizitäten .r j m jTrjmj

Online-Phase; Eingabe: q(x)

  1. Faktor als .q ( x ) = 5 i = 0 ( x i - r ' i )q(x)q(x)=i=05(xiri)

  2. Speichern Sie dies als eine Liste verschiedener Wurzeln und ihrer jeweiligen Multiplizitäten .r ' j m ' jLrjmj

  3. Während nicht leer ist, entfernen Sie die nächste root / Multiplizität von und einer beliebigen ähnlichen Begriffen in .L T.LLT

  4. Lesen Sie aus der modifizierten Tabelle und geben Sie sie aus. T.p(x)modq(x)T


Andere Kommentare:

  • Natürlich möchten Sie die Tabelle sortieren und mit einer binären Suche (oder einem Baum) darauf zugreifen.T
  • (Sei der Grad von .) Wenn die Ausgabe in Koeffizientendarstellung sein soll, können Sie am Ende einfach eine Reihe von FFTs ausführen, um zu erhalten Zeit.p ( x ) p ( x ) mod q ( x ) ˜ O ( d )dp(x)p(x)modq(x)O~(d)
  • Abhängig davon, wie Sie es formalisieren, können Sie wahrscheinlich viele der verschiedenen Möglichkeiten vorberechnen, wie Sie die Begriffe in zuvor neu kombinieren würden (dynamischer Programmierstil), sodass die meisten (oder alle) Multiplikationen nur Nachschlagen sind. Die dominierenden Kosten sind dann die Anzahl der Suchvorgänge oder ungefähr . Wenn , ist dies nur eine Handvoll konkreter arithmetischer Operationen.O ( log d ) d = 1000TO(logd)d=1000
Daniel Apon
quelle
2
In welchem ​​Bereich berücksichtigen Sie p? Wie groß wird diese Darstellung im Hinblick auf das ursprüngliche Feld sein? Und wenn Sie sagen, Sie sollen aus der geänderten Tabelle und Ausgabe ablesen, was meinen Sie damit?
David Eppstein
2
Dies würde nur funktionieren, wenn Sie über ein Feld arbeiten, in dem sowohl als auch geteilt sind. Dies scheint jedoch von abhängig zu sein ; Insbesondere können Sie die Wurzeln nicht allein für vorberechnen . Darüber hinaus benötigt die Berechnung der Wurzeln von über ein so großes Feld (mindestens) Zeit;; Das ist nicht besser als der naive Algorithmus. q q p q | p |pqqpq|p|
David Harris