Algorytm Cantora-Zassenhausa – algorytm probabilistyczny faktoryzacji wielomianów o współczynnikach w ciele skończonym. Został opisany przez Davida Cantora i Hansa Zassenhausa w 1981.
Redukcja dowolnego wielomianu do poprawnego wejścia Faktoryzacja dowolnego wielomianu może być sprowadzona do przypadku bezkwadratowego poprzez obliczanie największego wspólnego dzielnika wielomianu i jego pochodnej. Sprowadzenie do przypadku wielomianów o czynnikach równych stopni jest dokonywane przez następujący algorytm:
Wejście: bezkwadratowy wielomian o współczynnikach w ciele -elementowym Wyjście: zbiór par takich, że jest iloczynem wszystkich czynników nierozkładalnych wielomianu stopnia 1. Przyjmij 2. Znajdź największy wspólny dzielnik wielomianów i może być on znaleziony algorytmem Euklidesa i przyjmij 3. Jeśli przyjmij oraz 4. Zwiększ o 1. 5. Jeśli przejdź do kroku 2. 6. Jeśli przyjmij
Opis algorytmu Wejście: bezkwadratowy wielomian stopnia o współczynnikach w ciele -elementowym, którego wszystkie nierozkładalne czynniki są wielomianami stopnia Wyjście: nietrywialny dzielnik wielomianu (w ponad połowie prób). 1. Wybierz losowy wielomian stopnia mniejszego niż 2. Przyjmij 3. Znajdź największy wspólny dzielnik wielomianów i jeśli nie jest on równy 1 lub to jest to szukany dzielnik.
Złożoność i poprawność Algorytm ma złożoność obliczeniową (czas oczekiwany).
Poprawność redukcji opiera się na fakcie: Wielomian jest iloczynem wszystkich wielomianów nierozkładalnych stopni dzielących
Poprawność algorytmu opiera się na faktach: Pierścień jest iloczynem prostym ciał Dla losowego wielomianu składowa wielomianu w danym z tych ciał jest zerem z prawdopodobieństwem
Bibliografia David G. Cantor, Hans Zassenhaus, A New Algorithm for Factoring Polynomials Over Finite Fields, 1981.
Kategoria:Ciała skończone Kategoria:Algorytmy