Polynomfaktorisierung in einem endlichen Körper nach Cantor-Zassenhaus

Dieser Online-Rechner findet irreduzible Faktoren eines univariaten Polynoms in einem endlichen Körper unter Verwendung des Cantor-Zassenhaus Algorithmus. Anfänglich führt er die Eindeutige Faktorisierung aus, um den Faktor zu finden, welcher weiter zerlegt werden kann. Falls es benötigt, wird schließlich eine Faktorisierung gleichen Grades angewendet. Dies wird unter dem Rechner beschrieben.

Polynomfaktorisierung in einem endlichen Körper nach Cantor-Zassenhaus

Ganzzahlige Polynomkoeffizient

Modul

Details anzeigen

berechnen

Eingabepolynom

 

Lösung

 

Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.

Download 

Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.

Download 

 Link  Abspeichern  Widget

Cantor-Zassenhaus Faktorisierungsalgorithmus

Dieser Algorithmus hat die besseren Eigenschaften für großen Module wie der ähnliche Berlecamp Faktorisierungsalgorithmus.

• Überprüfe ob das Polynom Quadratfrei ist
• Finde alle Faktoren für Eindeutige Faktorisierung
• Wende den Zerlegungsalgorithmus für jeden Faktor an, der einen größeren Grad hat als die Faktorisierung vom vorherigen Schritt.

Faktorisierungsalgorithmus für gleiche Grade

// u(x) - Input polynomial of degree rd 
//    which has r factors each 
//    of degree d in Fp field
// p - odd field order
// d - target factors degree
// r - number of target factors
s⟵ { u }
loop while size(s) less than r
        h ⟵ random polynomial 
                  of degree less than 2d
        g ⟵ h^(p^d-1/2) -1 mod u
        for each a in s do 
              if deg(a) greater than d 
                    and gcd(g, a) ≠ 1 
                    and gcd(g, a) ≠ a then
                       remove a from s
                       add gcd(g,a) to s
                       add a/gcd(g,a) to s
              end if
         end do
end loop
output s