Algorytm Berlekampa
Algorytm Berlekampa to metoda faktoryzacji wielomianów z współczynnikami w ciele skończonym, opisana przez Elwyna Berlekampa w roku 1967.
Opis algorytmu
Wejście: wielomian
f
{\displaystyle f}
o stopniu
m
{\displaystyle m}
z współczynnikami w ciele
q
{\displaystyle q}
-elementowym.
Wyjście: nietrywialny dzielnik wielomianu lub informacja, że jest on potęgą wielomianu nierozkładalnego.
1. Utwórz macierz
Q
{\displaystyle Q}
o wymiarach
m
×
m
,
{\displaystyle m\times m,}
w której
i
{\displaystyle i}
-ta kolumna przedstawia
z
q
i
mod
f
.
{\displaystyle z^{qi}{\bmod {f}}.}
2. Znajdź bazę jądra przekształcenia liniowego
Q
−
I
;
{\displaystyle Q-I;}
Można to osiągnąć przy użyciu eliminacji Gaussa.
3. Dla dowolnego nieskalarnego wielomianu
g
{\displaystyle g}
(jeśli nie istnieje, to wielomian jest potęgą wielomianu nierozkładalnego) reprezentowanego przez wektor z bazy, dla każdego elementu
s
∈
G
F
(
q
)
,
{\displaystyle s\in GF(q),}
znajdź największy wspólny dzielnik wielomianów
f
{\displaystyle f}
i
g
−
s
{\displaystyle g-s}
(dla pewnego
s
{\displaystyle s}
będzie to poszukiwany nietrywialny dzielnik); może być on znaleziony przy pomocy algorytmu Euklidesa.
Złożoność i poprawność
Algorytm ma złożoność obliczeniową
O
(
m
2
(
m
+
q
)
(
log
(
q
)
)
2
)
.
{\displaystyle O(m^{2}(m+q)(\log(q))^{2}).}
Poprawność algorytmu opiera się na następujących stwierdzeniach:
g
(
z
)
q
−
g
(
z
)
=
∏
s
∈
G
F
(
q
)
(
g
(
z
)
−
s
)
,
{\displaystyle g(z)^{q}-g(z)=\prod _{s\in GF(q)}(g(z)-s),}
dla
s
≠
t
{\displaystyle s\neq t}
wielomiany
g
−
s
{\displaystyle g-s}
i
g
−
t
{\displaystyle g-t}
są względnie pierwsze,
f
(
z
)
=
∏
s
∈
G
F
(
q
)
g
c
d
(
f
(
z
)
,
g
(
z
)
−
s
)
.
{\displaystyle f(z)=\prod _{s\in GF(q)}gcd(f(z),g(z)-s).}
Bibliografia
Berlekamp, Elwyn R., Factoring Polynomials Over Finite Fields, 1967.
