Home Online Manual
Top
Back: BerlekampMassey
Forward: sparseInterpolation
FastBack:
FastForward:
Up: ffmodstd_lib
Top: Singular Manual
Contents: Table of Contents
Index: Index
About: About this document

D.15.14.5 modberlekampMassey

Procedure from library ffmodstd.lib (see ffmodstd_lib).

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

Return:
The minimal polynomial f (w.r.t. the i-th variable) generated by the sequence (L[j]), j = 1, 2, ... .

Note:
The procedure first construct polynomials f and g of degrees size(L) and size(L)-1, respectively from the sequence L[j] (elements from the field Q) for j>0 as described in [1]. It then returns the denominator polynomial d obtained by applying the SINGULAR command fareypoly to the input (g,f). If the ground ring has n variables, the procedure returns d in a polynomial ring k[var(i)] (k is a field) for some i<=n. In this case, an optional parameter i (default 0) can be provided.

References:

[1] Nadia Ben Atti, Gema M. Diaz-Toca and Henri Lombardi: The Berlekamp-Massey Algorithm Revisited, 2000.

Example:
 
LIB "ffmodstd.lib";
ring rr=0, (x,y,z), dp;
list L = 150,3204,79272,2245968, 70411680, 2352815424, 81496927872;
modberlekampMassey(L);// default w.r.t x
==> x3-66x2+1296x-7776
modberlekampMassey(L,3);// returns an ouput in the ring Q[z]
==> z3-66z2+1296z-7776
See also: BerlekampMassey.