Algorytm Berlekampa

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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

Opis algorytmu[edytuj | edytuj kod]

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ść[edytuj | edytuj kod]

Algorytm ma złożoność obliczeniową .

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

  • .
  • dla wielomiany i są względnie pierwsze.
  • .

Bibliografia[edytuj | edytuj kod]

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