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

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 $f$ o współczynnikach w ciele $q$-elementowym

Wyjście: zbiór par $(g,d)$ takich, że $g$ jest iloczynem wszystkich czynników nierozkładalnych wielomianu $f$ stopnia $d.$

1. Przyjmij $i:=1,$ $S:=\emptyset ,$ $h:=f.$

2. Znajdź największy wspólny dzielnik wielomianów $h$ i $x^{q^{i}}-x,$ może być on znaleziony algorytmem Euklidesa i przyjmij $g=gcd(h,x^{q^{i}}-x).$

3. Jeśli $deg(g)>0,$ przyjmij $S:=S\cup (g,i)$ oraz $h:=h/g.$

4. Zwiększ $i$ o 1.

5. Jeśli $deg(h)\geqslant 2i$ przejdź do kroku 2.

6. Jeśli $deg(h)>0$ przyjmij $S:=S\cup (h,deg(h)).$

Opis algorytmu

Wejście: bezkwadratowy wielomian $f$ stopnia $m=rd$ o współczynnikach w ciele $q$-elementowym, którego wszystkie nierozkładalne czynniki są wielomianami stopnia $d,$

Wyjście: nietrywialny dzielnik wielomianu (w ponad połowie prób).

1. Wybierz losowy wielomian $h$ stopnia mniejszego niż $m.$

2. Przyjmij $g:=h^{{\frac {q^{d}-1}{2}}-1}.$

3. Znajdź największy wspólny dzielnik wielomianów $f$ i $g;$ jeśli nie jest on równy 1 lub $f,$ to jest to szukany dzielnik.

Złożoność i poprawność

Algorytm ma złożoność obliczeniową $O(dm^{2}\log(q)\log(r))$ (czas oczekiwany).

Poprawność redukcji opiera się na fakcie:

• Wielomian $x^{q^{i}}-x$ jest iloczynem wszystkich wielomianów nierozkładalnych stopni dzielących $i.$

Poprawność algorytmu opiera się na faktach:

• Pierścień $\mathbb {F} [x]/f$ jest iloczynem prostym ciał $\mathbb {F} [x]/f_{i}.$
• Dla losowego wielomianu $h$ składowa wielomianu $g$ w danym z tych ciał jest zerem z prawdopodobieństwem ${\frac {q^{d}-1}{2q^{d}}}.$

Bibliografia

• David G. Cantor, Hans Zassenhaus, A New Algorithm for Factoring Polynomials Over Finite Fields, 1981.