Алгоритм Берлекампа – Цассенхауза - Berlekamp–Zassenhaus algorithm

В математика, в частности в вычислительная алгебра, то Алгоритм Берлекампа – Цассенхауза является алгоритм для факторинга многочлены над целые числа, названный в честь Элвин Берлекамп и Ганс Цассенхаус. Как следствие Лемма Гаусса, это сводится к решению проблемы также и над рациональными числами.

Алгоритм начинается с нахождения факторизаций по подходящим конечные поля с помощью Лемма Гензеля поднять решение по модулю простогоп к удобной мощностип. После этого правильные факторы находятся в их подмножестве. Худший случай этого алгоритма экспоненциально зависит от числа факторов.

Ван Хойдж (2002) улучшил этот алгоритм, используя LLL алгоритм, существенно сокращая время, необходимое для выбора правильных подмножеств модап факторы.

Рекомендации

• Берлекамп, Э. (1967), «Факторизация многочленов над конечными полями» (PDF), Технический журнал Bell System, 46: 1853–1859, Дои:10.1002 / j.1538-7305.1967.tb03174.x, МИСТЕР  0219231.
• Берлекамп, Э. (1970), "Факторизация многочленов над большими конечными полями", Математика вычислений, 24: 713–735, Дои:10.2307/2004849, JSTOR  2004849, МИСТЕР  0276200.
• Кантор, Дэвид Дж .; Цассенхаус, Ганс (1981), "Новый алгоритм факторизации многочленов над конечными полями", Математика вычислений, 36 (154): 587–592, Дои:10.2307/2007663, JSTOR  2007663, МИСТЕР  0606517.
• Geddes, K. O .; Czapor, S. R .; Лабан, Г. (1992), Алгоритмы компьютерной алгебры, Бостон, Массачусетс: Kluwer Academic Publishers, Дои:10.1007 / b102438, ISBN  0-7923-9259-0, МИСТЕР  1256483.
• Ван Хой, Марк (2002), "Факторизация многочленов и задача о рюкзаке", Журнал теории чисел, 95 (2): 167–189, Дои:10.1016 / S0022-314X (01) 92763-5, МИСТЕР  1924096.
• Цассенхаус, Ганс (1969), "О факторизации Гензеля. I", Журнал теории чисел, 1: 291–311, Дои:10.1016 / 0022-314X (69) 90047-X, МИСТЕР  0242793.

внешняя ссылка

• Домазет, Харис. «Алгоритм Берлекампа-Цассенхауза». MathWorld.

Смотрите также

• Алгоритм Берлекампа