Algorytm Berlekampa

Algorytm Berlekampa - algorytm faktoryzacji wielomianów o współczynnikach w ciele skończonym. Został opisany przez Elwyna Berlekampa w 1967.

Opis algorytmu

Wejście: wielomian $f$ stopnia $\scriptstyle m$ o współczynnikach w ciele $\scriptstyle q$-elementowym,

Wyjście: nietrywialny dzielnik wielomianu lub informacja, że jest on potęgą wielomianu nierozkładalnego.

1. Utwórz macierz $Q$ wielkości $\scriptstyle m\times m$, której $\scriptstyle i$-ta kolumna przedstawia $z^{qi}\,mod\,f$.

2. Znajdź bazę jądra przekształcenia liniowego $Q-I$; można tego dokonać używając eliminacji Gaussa.

3. Dla dowolnego nieskalarnego wielomianu $g$ (jeśli nie istnieje, to wielomian jest potęgą wielomianu nierozkładalnego) reprezentowanego przez wektor z bazy, dla każdego elementu $\scriptstyle s\in GF(q)$, znajdź największy wspólny dzielnik wielomianów $f$ i $g-s$ (dla pewnego $s$ będzie to poszukiwany nietrywialny dzielnik); może być on znaleziony algorytmem Euklidesa.

Złożoność i poprawność

Algorytm ma złożoność obliczeniową $O(m^{2}(m+q)(log(q))^{2})$.

Jego poprawność opiera się na następujących faktach:

• $g(z)^{q}-g(z)=\prod _{s\in GF(q)}(g(z)-s)$.
• dla $s\neq t$ wielomiany $g-s$ i $g-t$ są względnie pierwsze.
• $f(z)=\prod _{s\in GF(q)}gcd(f(z),g(z)-s)$.

Źródła

• Berlekamp, Elwyn R. "Factoring Polynomials Over Finite Fields"(1967).