Алгоритм Бэрликэмпа-Мэсси

1. Задача: дана последовательность длины n, порожденная линейным реккурентным соотношением длины k (n >= 2k)
2. Достаточно взять первые 2k чисел, т.е. пусть n = 2k и асимптотика будет от k
3. Простое решение за O(k³) -- Гаусс.
4. Алгоритм Бэрликэмпа-Мэсси решает данную задачу за O(k²)
1. 2k чисел − многочлен A. k неизвестных − многочлен P
2. F_k = 5F_k-1 + 7F_k-2 ⇒ P(x) = 7x² + 5x - 1, где 7 и 5 будут неизвестными.
3. Рассмотрим A(x)P(x). Все промежуточные коэффициенты будут равны нулю.
4. A(x)P(x) = R(x) + x^2kS(x), где degR, degS < k
5. Даны, A(x) и x^2k, найти P(x), R(x), S(x) можно расширенным алгоритмом Евклида.