Алгоритм Берлекэмпа–Месси над коммутативными артиновыми кольцами главных идеалов

Представлен алгоритм, позволяющий по заданному отрезку длины $l$ над коммутативным артиновым кольцом главных идеалов $R$ построить унитарный многочлен наименьшей степени, порождающий этот отрезок. Трудоёмкость алгоритма составляет $O(l^2n)$ операций кольца, где $n$ — индекс нильпотентности радикала кольца $R$. Алгоритм применяется для построения канонической системы образующих идеала всех многочленов, аннулирующих заданную линейную рекуррентную последовательность над кольцом $R$.