Algoritmus Berlekamp – Zassenhaus - Berlekamp–Zassenhaus algorithm

v matematika, zejména v výpočetní algebra, Algoritmus Berlekamp – Zassenhaus je algoritmus pro factoring polynomy přes celá čísla, pojmenoval podle Elwyn Berlekamp a Hans Zassenhaus. Jako důsledek Gaussovo lema, to znamená řešení problému také v racionálním smyslu.

Algoritmus začíná nalezením faktorizace nad vhodnou konečná pole použitím Henselův lemma zvednout řešení z modulo primep na pohodlnou sílup. Poté se naleznou správné faktory jako jejich podmnožina. Nejhorší případ tohoto algoritmu je exponenciální v počtu faktorů.

Van Hoeij (2002) vylepšil tento algoritmus pomocí Algoritmus LLL, což podstatně zkracuje čas potřebný k výběru správných podmnožin modp faktory.

Reference

  • Berlekamp, ​​E. R. (1967), "Faktorování polynomů přes konečná pole" (PDF), Technický deník Bell System, 46: 1853–1859, doi:10.1002 / j.1538-7305.1967.tb03174.x, PAN  0219231.
  • Berlekamp, ​​E. R. (1970), "Faktorování polynomů nad velkými konečnými poli", Matematika výpočtu, 24: 713–735, doi:10.2307/2004849, JSTOR  2004849, PAN  0276200.
  • Cantor, David G .; Zassenhaus, Hans (1981), „Nový algoritmus pro dělení polynomů na konečná pole“, Matematika výpočtu, 36 (154): 587–592, doi:10.2307/2007663, JSTOR  2007663, PAN  0606517.
  • Geddes, K. O .; Czapor, S. R .; Labahn, G. (1992), Algoritmy pro počítačovou algebru, Boston, MA: Kluwer Academic Publishers, doi:10.1007 / b102438, ISBN  0-7923-9259-0, PAN  1256483.
  • Van Hoeij, Mark (2002), „Faktoring polynomů a problém s batohem“, Žurnál teorie čísel, 95 (2): 167–189, doi:10.1016 / S0022-314X (01) 92763-5, PAN  1924096.
  • Zassenhaus, Hans (1969), "O Henselově faktorizaci. I", Žurnál teorie čísel, 1: 291–311, doi:10.1016 / 0022-314X (69) 90047-X, PAN  0242793.

externí odkazy

Viz také