Ein zufallsbasierter Algorithmus zur Faktorisierung von Polynomen über endlichen Körpern, üblicherweise in zwei Phasen ausgeführt: Distinct-Degree-Faktorisierung gefolgt vom Equal-Degree-Splitting mittels zufälliger Polynome und Exponentiation in der multiplikativen Gruppe, um Faktoren mit hoher Wahrscheinlichkeit zu trennen.

Prinzip

Probabilistisches Sampling im Quotientenring und gruppentheoretische Exponentiation verwenden: zufälliges a(x) wählen, a(x)^{(q^d−1)/2} modulo f berechnen (oder analoge Gruppentests) und ggT mit f bilden, um Faktoren vom Grad d mit konstanter Wahrscheinlichkeit abzutrennen; iterieren bis zur vollständigen Faktorisierung.

Demonstration

Nachdem die Distinct-Degree-Zerlegung ein Produkt von Faktoren geliefert hat, deren irreduzible Komponenten alle Grad d haben, wählt man zufällige a(x) und berechnet ggT(a^{(q^d-1)/2}-1, f); eine zufällige Wahl trennt den Faktor mit konstanter Erfolgserwartung in zwei nichttriviale Faktoren, sodass wenige Versuche genügen.

Fehlanwendung

Das Vernachlässigen der quadratfreien Vorverarbeitung oder der Distinct-Degree-Trennung vor dem Versuch des Equal-Degree-Splittings verschlechtert die Erfolgswahrscheinlichkeiten und kann falsche Faktorspalten ergeben; vom Erfolg in einem einzelnen Versuch auszugehen führt zu schlechtem Worst-Case-Verhalten, da der Algorithmus probabilistisch ist.

Konsequenz

Cantor–Zassenhaus liefert einen Algorithmus mit gutem erwarteten Laufzeitverhalten und geringem Speicherbedarf zur Faktorisierung über endlichen Körpern und skaliert praktisch gut für große Felder und Grade; seine Zufälligkeit macht ihn schnell und einfach zu implementieren.

Umkehrung

Umkehrbar durch deterministische lineare Algebra-Ansätze (Berlekamp) oder deterministische modulare Algorithmen: wo Cantor–Zassenhaus Zufälligkeit gegen Geschwindigkeit tauscht, liefert die Umkehrung Determinismus auf Kosten schwererer linear-algebraischer Arbeit oder komplexerer Algorithmen.

Abgrenzung

Gilt für Polynome über endlichen Körpern und setzt zugängliche Feldarithmetik voraus; seine probabilistischen Garantien sind asymptotisch und hängen von Feldgröße und Grad ab — bei sehr kleinen Feldern oder strukturierten Polynomen sind zusätzliche Vorsichtsmaßnahmen oder viele Versuche erforderlich.

Semantische Spannung

Es besteht praktische Spannung zwischen zufallsbasiertem Splitting (schneller Durchschnittsfall, einfache Struktur) und deterministischen Algorithmen (garantiertes Verhalten, aber oft ressourcenintensiver); Cantor–Zassenhaus wird in der Praxis oft wegen Einfachheit und Geschwindigkeit bevorzugt.

Synthese

Cantor–Zassenhaus ist ein zweistufiges, zufallsbasiertes Faktorisierungsverfahren, das zunächst nach Graden trennt und dann gleichgradige Komponenten durch zufällige Auswahl und Gruppenexponentiation spaltet: Durch probabilistisches Trennen und wiederholte ggT-Operationen erreicht es effiziente erwartete Laufzeit bei der Faktorisierung über endlichen Körpern.