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:=\mathrm{\varnothing },$ $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)⩾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(d{m}^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ń $𝔽[x]/f$ jest iloczynem prostym ciał $𝔽[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.