Polynomfaktorisierung in einem endlichen Körper nach Cantor-Zassenhaus
Dieser Online-Rechner findet Faktoren eines Polynoms mit dem Cantor-Zassenhaus Algorithmus.
Der Inhalt ist unter der Creative Commons Namensnennung / Weitergabe unter gleichen Bedingungen 3.0 (nicht portiert) lizenziert. Dies bedeutet, dass Sie diesen Inhalt unter den gleichen Lizenzbedingungen frei weitergeben oder ändern dürfen, jedoch mit Zuordnung zum Entwickler indem Sie einen Hyperlink auf Ihrer Webseite zu dieser Arbeit https://de.planetcalc.com/8372/ platzieren. Des Weiteren ändern Sie bitte keine Verweise auf das Originalwerk (falls vorhanden) das in diesem Inhlat vorhanden ist.
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
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
Kommentare