# Singular

#### D.15.14.4 BerlekampMassey

Procedure from library `ffmodstd.lib` (see ffmodstd_lib).

Usage:
BerlekampMassey(L, i[, M]); L list, i int, M list

Return:
a list Tr where f:=Tr[1] is the minimal polynomial (w.r.t. the i-th variable) generated by the sequence (L[j]), 1<=j<= Tr[2], if the length of the sequence is long enough. In this case, the coefficients c_i of the polynomial f satisfy the relation -L[j+t] = c_0*L[j] + ... + c_{t-1}*L[j+t-1] for all j >=1 where t=deg(f).

Note:
The procedure applies the Berlekamp/Massey algorithm to the sequence L[j] (elements from the field Q) for j>0 and returns a polynomial f. If the polynomial f splits into linear factors with no multiplicity greater than one, then we say that the length of the sequence L is long enough. If this polynomial does not split into linear factors, an optional parameter M = BerlekampMassey(L',i) can be provided to add more elements to the sequence.

References:

[1] E. Kaltofen and W.-s. Lee: Early termination in sparse interpolation algorithms. J. Symb. Comput. 36, 365-400 (2003).
[2] E. Kaltofen, W.-s. Lee and A. A. Lobo: Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm. Proc. ISSAC (ISSAC '00), 192-201 (2000).

Example:
 ```LIB "ffmodstd.lib"; ring rr=0,x,dp; list L = 150,3204,79272,2245968; list Tr = BerlekampMassey(L,1); Tr[1]; ==> 117288/209x2-10662/209x+1 factorize(Tr[1]); //not linearly factored ==> [1]: ==> _[1]=1/209 ==> _[2]=117288x2-10662x+209 ==> [2]: ==> 1,1 list L1 = 70411680, 2352815424, 81496927872; Tr = BerlekampMassey(L1,1,Tr); // increase the length of L by size(L1) Tr[1]; ==> x3-66x2+1296x-7776 factorize(Tr[1]); //linearly factored and has distinct roots ==> [1]: ==> _[1]=1 ==> _[2]=x-18 ==> _[3]=x-36 ==> _[4]=x-12 ==> [2]: ==> 1,1,1,1 Tr[2]; //the length of the sequence required to generate Tr[1] ==> 6 ```