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 stopnia o współczynnikach w ciele -elementowym, Wyjście: nietrywialny dzielnik wielomianu lub informacja, że jest on potęgą wielomianu nierozkładalnego. 1. Utwórz macierz wielkości której -ta kolumna przedstawia 2. Znajdź bazę jądra przekształcenia liniowego można tego dokonać używając eliminacji Gaussa. 3. Dla dowolnego nieskalarnego wielomianu (jeśli nie istnieje, to wielomian jest potęgą wielomianu nierozkładalnego) reprezentowanego przez wektor z bazy, dla każdego elementu znajdź największy wspólny dzielnik wielomianów i (dla pewnego będzie to poszukiwany nietrywialny dzielnik); może być on znaleziony algorytmem Euklidesa.
Złożoność i poprawność Algorytm ma złożoność obliczeniową
Jego poprawność opiera się na następujących faktach:
dla wielomiany i są względnie pierwsze,
Bibliografia Berlekamp, Elwyn R., Factoring Polynomials Over Finite Fields, 1967.
Kategoria:Ciała skończone Kategoria:Algorytmy