Algorytm Cantora-Zassenhausa

Algorytm Cantora-Zassenhausa to probabilistyczny sposób na faktoryzację wielomianów z współczynnikami w ciele skończonym, opisany przez Davida Cantora i Hansa Zassenhausa w 1981 roku.

Redukcja dowolnego wielomianu do poprawnego wejścia

Faktoryzacja każdego wielomianu może zostać uproszczona do przypadku bezkwadratowego poprzez obliczenie największego wspólnego dzielnika między wielomianem a jego pochodną. Proces ten polega na przekształceniu do przypadku wielomianów o czynnikach równych stopniom zgodnie z poniższym algorytmem:

Wejście: bezkwadratowy wielomian f o współczynnikach w ciele q-elementowym

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

  1. Ustaw i := 1, S := ∅, h := f.
  2. Oblicz największy wspólny dzielnik wielomianów h i xqi – x przy pomocy algorytmu Euklidesa i przyjmij g = gcd(h, xqi – x).
  3. Jeśli deg(g) > 0, to przyjmij S := S ∪ (g, i) oraz h := h/g.
  4. Zwiększ i o 1.
  5. Jeśli deg(h) ≥ 2i, wróć do kroku 2.
  6. Jeśli deg(h) > 0, przyjmij S := S ∪ (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 mają stopień d.

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

  1. Wybierz losowy wielomian h stopnia mniejszego niż m.
  2. Ustal g := h(qd – 1)/2 – 1.
  3. Oblicz największy wspólny dzielnik wielomianów f i g; jeśli nie wynosi on 1 lub f, to jest to szukany dzielnik.

Złożoność i poprawność

Algorytm ma złożoność obliczeniową O(dm2 log(q) log(r)) (w oczekiwanym czasie).

Poprawność redukcji opiera się na stwierdzeniu, że wielomian xqi – x jest iloczynem wszystkich wielomianów nierozkładalnych stopni dzielących i.

Poprawność algorytmu opiera się na twierdzeniach dotyczących pierścienia F[x]/f jako iloczynu prostego ciał F[x]/fi.

Dla losowego wielomianu h, jego składowa g w danym ciele ma zerowe prawdopodobieństwo wynoszące (qd – 1)/(2qd).

Bibliografia

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

Przeczytaj u przyjaciół: