Algorytm Berlekampa

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

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

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

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

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

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

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

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

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

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