Алгоритм Берлекэмпа
Алгоритм Берлекэмпа — алгоритм, предназначенный для факторизации унитарных многочленов над конечным полем. Разработан Элвином Берлекэмпом в 1967 году. Может использоваться также для проверки неприводимости многочленов над конечными полями.
Основная идея алгоритма заключается в возможности представления исходного многочлена в виде произведения наибольших общих делителей самого многочлена и некоторых многочленов, которые с точностью до свободного члена являются formula_1-разлагающими.

Алгоритм Берлекэмпа имеет большую вычислительную сложность, поэтому был разработан ряд дополнительных методов, позволяющих сократить количество необходимых математических операций. Однако, несмотря на свою сложность, алгоритм Берлекэмпа был реализован в системах компьютерной алгебры. Алгоритм нашёл широкое применение в теории кодирования и в изучении линейных рекуррентных соотношений в конечных полях. Имеется много вычислительных задач в алгебре и в теории чисел, которые так или иначе связаны с разложением многочленов над конечными полями, например, разложение на множители многочленов над кольцом целых чисел, отыскание разложения простого рационального числа в поле алгебраических чисел, вычисление группы Галуа некоторого уравнения над полем рациональных чисел и построение расширений полей.
Q188804
факторизации
Concept
Q43260
унитарных
Concept
Q4298929
многочленов над конечным полем
UNK
Q1314603
Элвином Берлекэмпом
PER
Q632963
1967 году
Concept
Q1476663
неприводимости многочленов
Concept
Q1062839
теории кодирования
Concept
Q740970
рекуррентных соотношений
Concept
Q1996100
разложением многочленов
Concept
Q161172
кольцом целых чисел
Concept
Q1244890
простого рационального числа
Concept
Q730384
группы Галуа
Concept
Q821001
Алгоритм Берлекэмпа
Concept
Q821001
Алгоритм Берлекэмпа
Concept
1967-01-01T00:00:00Z^^http://www.w3.org/2001/XMLSchema#dateTime
в 1967
DATE
+1^^http://www.w3.org/2001/XMLSchema#decimal
1
NUMBER
named after
publication date