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.