# 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 is the minimal polynomial (w.r.t. the i-th variable) generated by the sequence (L[j]), 1<=j<= Tr, 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:

 E. Kaltofen and W.-s. Lee: Early termination in sparse interpolation algorithms. J. Symb. Comput. 36, 365-400 (2003).
 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; ==> 117288/209x2-10662/209x+1 factorize(Tr); //not linearly factored ==> : ==> _=1/209 ==> _=117288x2-10662x+209 ==> : ==> 1,1 list L1 = 70411680, 2352815424, 81496927872; Tr = BerlekampMassey(L1,1,Tr); // increase the length of L by size(L1) Tr; ==> x3-66x2+1296x-7776 factorize(Tr); //linearly factored and has distinct roots ==> : ==> _=1 ==> _=x-18 ==> _=x-36 ==> _=x-12 ==> : ==> 1,1,1,1 Tr; //the length of the sequence required to generate Tr ==> 6 ```

### Misc 