Пример применения алгоритма Берлекэмпа-Месси

[wataru]

Стоило бы немного определений и контекста добавить.

А так, даже на википедии этот алгоритм объяснен лучше.

[DoomeR18G]

Факт

[VladimirLadynev]

Блин же ж. Вы сначала по-простому объясните, что за многочлен-то такой и зачем он нужен.

[Morgana0_0]

Зачем его искать вопрос хороший. Всех ответов на этот вопрос я не знаю. Мною рассматривалась просто учебная задача из книжки, но вообще минимальных многочлен позволяет построить самый короткий регистр для генерации соответствующей ЛРП, что в свою очередь ускоряет работу и тратит меньше памяти.

[alvoskov]

Насколько я понимаю, это - тот самый алгоритм, который используется в тестах вроде Linear Complexity пакета статистических тестов TestU01 для того, чтобы "поймать" вихрь Мерсенна или xorshift64? Если да, то можно ли посмотреть на алгоритм Берлекэмпа-Месси как на высокооптимизированный для конкретной задачи (поиск коэффициентов рекуррентного соотношения) метод Гаусса, дающего уменьшение сложности по времени с O(n^4) до O(n^2)?