D.4.9.4 BerlekampMassey

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).

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-36
==>    _[3]=x-18
==>    _[4]=x-12
==> [2]:
==>    1,1,1,1
Tr[2]; //the length of the sequence required to generate Tr[1]
==> 6