Tekst źródłowy strony Algorytm Cantora-Zassenhausa

'''Algorytm Cantora-Zassenhausa''' – [[algorytm probabilistyczny]] [[Rozkład na czynniki|faktoryzacji]] [[wielomian]]ów o współczynnikach w [[ciało skończone|ciele skończonym]]. Został opisany przez Davida Cantora i [[Hans Julius Zassenhaus|Hansa Zassenhausa]] w [[1981]].

== Redukcja dowolnego wielomianu do poprawnego wejścia ==
Faktoryzacja dowolnego wielomianu może być sprowadzona do przypadku bezkwadratowego poprzez obliczanie [[największy wspólny dzielnik|największego wspólnego dzielnika]] wielomianu i jego [[Pochodna formalna|pochodnej]]. Sprowadzenie do przypadku wielomianów o czynnikach równych stopni jest dokonywane przez następujący algorytm:

: Wejście: bezkwadratowy wielomian <math>f</math> o współczynnikach w ciele <math>q</math>-elementowym
: Wyjście: zbiór par <math>(g,d)</math> takich, że <math>g</math> jest iloczynem wszystkich czynników [[Wielomian nierozkładalny|nierozkładalnych]] wielomianu <math>f</math> stopnia <math>d.</math>
: 1. Przyjmij <math>i:=1,</math> <math>S:=\emptyset,</math> <math>h:=f.</math>
: 2. Znajdź największy wspólny dzielnik wielomianów <math>h</math> i <math>x^{q^i} - x,</math> może być on znaleziony [[Algorytm Euklidesa|algorytmem Euklidesa]] i przyjmij <math>g=gcd(h,x^{q^i} - x).</math>
: 3. Jeśli <math>deg(g)>0,</math> przyjmij <math>S:=S \cup (g,i)</math> oraz <math>h:=h/g.</math>
: 4. Zwiększ <math>i</math> o 1.
: 5. Jeśli <math>deg (h) \geqslant 2i</math> przejdź do kroku 2.
: 6. Jeśli <math>deg (h) > 0</math> przyjmij <math>S:=S \cup (h,deg(h)).</math>

== Opis algorytmu ==
: Wejście: bezkwadratowy wielomian <math>f</math> stopnia <math>m = r d</math> o współczynnikach w ciele <math>q</math>-elementowym, którego wszystkie nierozkładalne czynniki są wielomianami stopnia <math>d,</math>
: Wyjście: nietrywialny dzielnik wielomianu (w ponad połowie prób).
: 1. Wybierz losowy wielomian <math>h</math> stopnia mniejszego niż <math>m.</math>
: 2. Przyjmij <math>g:= h^{\frac{q^d-1}{2}-1}.</math>
: 3. Znajdź największy wspólny dzielnik wielomianów <math>f</math> i <math>g;</math> jeśli nie jest on równy 1 lub <math>f,</math> to jest to szukany dzielnik.

== Złożoność i poprawność ==
Algorytm ma złożoność obliczeniową <math>O(d m^2 \log(q)\log(r))</math> ([[Wartość oczekiwana|czas oczekiwany]]).

Poprawność redukcji opiera się na fakcie:
* Wielomian <math>x^{q^i} - x</math> jest iloczynem wszystkich wielomianów nierozkładalnych stopni dzielących <math>i.</math>

Poprawność algorytmu opiera się na faktach:
* Pierścień <math>\mathbb{F} [x]/f</math> jest iloczynem prostym ciał <math>\mathbb{F} [x]/f_i.</math>
* Dla losowego wielomianu <math>h</math> składowa wielomianu <math>g</math> w danym z tych ciał jest zerem z prawdopodobieństwem <math>\frac{q^d-1}{2 q^d}.</math>

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

{{SORTUJ:Cantora-Zassenhausa, algorytm}}
[[Kategoria:Ciała skończone]]
[[Kategoria:Algorytmy]]