## [Cantor–Zassenhaus-Algorithmus](/de/node/63530) Definition 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 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 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 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 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 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 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 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 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.