Znajdź największy wspólny dzielnik wielomianów i jeśli nie jest on równy 1 lub to jest to szukany dzielnik.
Złożoność i poprawność Algorytm ma złożoność obliczeniową (czas oczekiwany).
Poprawność redukcji opiera się na fakcie: Wielomian jest iloczynem wszystkich wielomianów nierozkładalnych stopni dzielących
Poprawność algorytmu opiera się na faktach: Pierścień jest iloczynem prostym ciał Dla losowego wielomianu składowa wielomianu w danym z tych ciał jest zerem z prawdopodobieństwem
Bibliografia David G. Cantor, Hans Zassenhaus, A New Algorithm for Factoring Polynomials Over Finite Fields, 1981.
Kategoria:Ciała skończone Kategoria:Algorytmy