|
D.4.8.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-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
|
|