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 $\scriptstyle 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)\geq 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 $\scriptstyle m=rd$ o współczynnikach w ciele $\scriptstyle q$-elementowym, którego wszystkie nierozkładalne czynniki są wielomianami stopnia $\scriptstyle 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}}}$.

Źródła

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