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 $m$ o współczynnikach w ciele $q$-elementowym,

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

1. Utwórz macierz $Q$ wielkości $m\times m,$ której $i$-ta kolumna przedstawia $z^{qi}{\bmod {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 $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).$

Bibliografia

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