Module: sage.matrix.berlekamp_massey
Minimal Polynomials of Linear Recurrence Sequences
Author: William Stein
Module-level Functions
a) |
Use the Berlekamp-Massey algorithm to find the minimal polynomial of a linearly recurrence sequence a.
The minimal polynomial of a linear recurrence
is by
definition the unique monic polynomial
, such that if
satisfies a linear recurrence
(for all
), then
divides the
polynomial
.
Input:
sage: berlekamp_massey([1,2,1,2,1,2]) x^2 - 1 sage: berlekamp_massey([GF(7)(1),19,1,19]) x^2 + 6 sage: berlekamp_massey([2,2,1,2,1,191,393,132]) x^4 - 36727/11711*x^3 + 34213/5019*x^2 + 7024942/35133*x - 335813/1673 sage: berlekamp_massey(prime_range(2,38)) x^6 - 14/9*x^5 - 7/9*x^4 + 157/54*x^3 - 25/27*x^2 - 73/18*x + 37/9
See About this document... for information on suggesting changes.