Algorytm Cantora-Zassenhausa
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 edytuj
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 edytuj
- 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ść edytuj
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 edytuj
- David G. Cantor, Hans Zassenhaus, A New Algorithm for Factoring Polynomials Over Finite Fields, 1981.