user
The **Berlekamp–Massey algorithm** is an efficient algorithm for finding the shortest linear feedback shift register (LFSR) that generates a given sequence over a finite field. It determines the minimal polynomial of a linearly recurrent sequence, which is crucial in applications like error-correcting codes, cryptography, and sequence analysis.

Overview

Given a sequence of elements 

s

0
,

s

1
,
…
,

s

n
−
1
{\displaystyle {\displaystyle s\_{0},s\_{1},\dots ,s\_{n-1}}}
 from a finite field, the Berlekamp–Massey algorithm computes the shortest LFSR, characterized by its connection polynomial 

C
(
x
)
=
1
+

c

1
x
+

c

2

x

2
+
⋯
+

c

L

x

L
{\displaystyle {\displaystyle C(x)=1+c\_{1}x+c\_{2}x^{2}+\dots +c\_{L}x^{L}}}
, such that the sequence satisfies the recurrence relation:

:   s

    i
    +
    L
    =
    −

    ∑

    k
    =
    1

    L

    c

    k

    s

    i
    +
    L
    −
    k
    {\displaystyle {\displaystyle s\_{i+L}=-\sum \_{k=1}^{L}c\_{k}s\_{i+L-k}}}

for all valid indices. The degree 

L
{\displaystyle {\displaystyle L}}
 of the polynomial is the *linear complexity* of the sequence, representing the length of the shortest LFSR.

History

The algorithm was independently developed by Elwyn Berlekamp in 1968 for decoding BCH codes and by James Massey in 1969 for cryptographic applications. It remains a cornerstone in coding theory and sequence analysis.

Algorithm Description

The Berlekamp–Massey algorithm iteratively constructs the connection polynomial by processing the input sequence element by element. It maintains a current polynomial 

C
(
x
)
{\displaystyle {\displaystyle C(x)}}
 and updates it whenever a discrepancy is found between the predicted and actual sequence values. The key steps are:

1. Initialize 

C
(
x
)
=
1
{\displaystyle {\displaystyle C(x)=1}}
, degree 

L
=
0
{\displaystyle {\displaystyle L=0}}
, and a temporary polynomial 

B
(
x
)
=
1
{\displaystyle {\displaystyle B(x)=1}}
.
2. For each sequence element 

s

i
{\displaystyle {\displaystyle s\_{i}}}
:

```
  * Compute the discrepancy 
  
    
      
        
          
            Δ
            =
            
              s
              
                i
              
            
            +
            
              ∑
              
                k
                =
                1
              
              
                L
              
            
            
              c
              
                k
              
            
            
              s
              
                i
                −
                k
              
            
          
        
      
    
    {\displaystyle {\displaystyle \Delta =s_{i}+\sum _{k=1}^{L}c_{k}s_{i-k}}}
  
.
  * If 
  
    
      
        
          
            Δ
            ≠
            0
          
        
      
    
    {\displaystyle {\displaystyle \Delta \neq 0}}
  
:
    * Update 
  
    
      
        
          
            C
            (
            x
            )
            ←
            C
            (
            x
            )
            −
            Δ
            x
            B
            (
            x
            )
          
        
      
    
    {\displaystyle {\displaystyle C(x)\leftarrow C(x)-\Delta xB(x)}}
  
.
    * If the discrepancy indicates a need for a longer LFSR (i.e., 
  
    
      
        
          
            2
            L
            ≤
            i
          
        
      
    
    {\displaystyle {\displaystyle 2L\leq i}}
  
), update 
  
    
      
        
          
            L
          
        
      
    
    {\displaystyle {\displaystyle L}}
  
 and adjust 
  
    
      
        
          
            B
            (
            x
            )
          
        
      
    
    {\displaystyle {\displaystyle B(x)}}
  
.

```

3. Output 

C
(
x
)
{\displaystyle {\displaystyle C(x)}}
 and 

L
{\displaystyle {\displaystyle L}}
.

The algorithm runs in 

O
(

n

2
)
{\displaystyle {\displaystyle O(n^{2})}}
 time, where 

n
{\displaystyle {\displaystyle n}}
 is the sequence length, and uses 

O
(
n
)
{\displaystyle {\displaystyle O(n)}}
 space.

Applications

* **Error Correction**: Used in decoding Reed–Solomon codes and BCH codes.
* **Cryptography**: Analyzes the linear complexity of sequences in stream ciphers to assess security.
* **Sequence Analysis**: Identifies patterns in sequences for signal processing and data compression.

Example

For the binary sequence 

0
,
0
,
1
,
1
,
0
,
1
,
0
{\displaystyle {\displaystyle 0,0,1,1,0,1,0}}
 over 

G
F
(
2
)
{\displaystyle {\displaystyle GF(2)}}
, the algorithm yields the connection polynomial 

C
(
x
)
=
1
+
x
+

x

3
{\displaystyle {\displaystyle C(x)=1+x+x^{3}}}
, indicating a linear complexity of 3.
assistant
**Translation of**: Python

```
# 20250510 Raku programming solution

constant MOD = 2;

sub berlekamp_massey(@a) {
   my ($n, $w, $delta, @ans_coef, @lst) = @a.elems - 1, 0;
   for 1 .. $n -> $i {
      my $tmp = 0;
      for ^@ans_coef.elems -> $j {
         if $i - 1 - $j >= 1 {
            $tmp = ($tmp + @a[$i - 1 - $j] * @ans_coef[$j]) % MOD;
         }
      }
      my $discrepancy = (@a[$i] - $tmp + MOD) % MOD;
      next if $discrepancy == 0;
      if $w == 0 {
         @ans_coef = (0 xx $i);
         $w = $i;
         $delta = $discrepancy;
         next;
      }
      my @now = @ans_coef;
      my $mul = $discrepancy * expmod($delta, MOD - 2, MOD);
      my $needed_len = @lst.elems + $i - $w;
      if @ans_coef.elems < $needed_len {
         @ans_coef.append: (0 xx ($needed_len - @ans_coef.elems));
      }
      if $i - $w - 1 >= 0 {
         @ans_coef[$i - $w - 1] = (@ans_coef[$i - $w - 1] + $mul) % MOD;
      }
      for ^@lst.elems -> $j {
         my $idx = $i - $w + $j;
         if $idx < @ans_coef.elems {
            my $term_to_subtract = ($mul * @lst[$j]) % MOD;
            @ans_coef[$idx] = (@ans_coef[$idx] - $term_to_subtract + MOD) % MOD;
         }
      }
      if @ans_coef.elems > @now.elems {
         @lst = @now;
         $w = $i;
         $delta = $discrepancy;
      }
   }
   return @ans_coef.map: { ($^x + MOD) % MOD };
}

sub calculate_term($m, @coef, @h) {
   if $m < @h.elems                { return (@h[$m] + MOD) % MOD }
   if ( my $k = @coef.elems ) == 0 { return 0 } 
   my @p_coeffs = (1, |@coef);
   sub poly_mul(@a, @b, $degree_k, @p_poly) {
      my @res = (0 xx (2 * $degree_k));
      for ^$degree_k X ^$degree_k -> ($i, $j) {
         next if @a[$i] == 0;
         @res[$i + $j] = (@res[$i + $j] + @a[$i] * @b[$j]) % MOD;
      }
      for ( 2 * $degree_k - 1 ... $degree_k ) -> $i {
         next if @res[$i] == 0; 
         my $term = @res[$i];
         @res[$i] = 0;
         for 0 .. $degree_k -> $j {
            if ( my $idx = $i - $j ) >= 0 { 
               @res[$idx] = (@res[$idx] + $term * @p_poly[$j]) % MOD; 
            }
         }
      }
      return @res[0 ... ^$degree_k];
   }
   my @f = (1, |(0 xx ($k - 1)));
   my @g = $k == 1 ?? (@p_coeffs[1],) !! (0, 1, |(0 xx ($k - 2)));
   my $power = $m;
   while $power > 0 {
      unless $power %% 2 { @f = poly_mul(@f, @g, $k, @p_coeffs) }
      @g = poly_mul(@g, @g, $k, @p_coeffs);
      $power div= 2;
   }
   my $final_ans = 0;
   for ^$k -> \k {
      if k+1 < @h.elems { $final_ans = ($final_ans + @h[k+1] * @f[k]) % MOD }
   } 
   return ($final_ans + MOD) % MOD;
}

sub solve {
   my @h_input = 0,0,1,1,0,1,0;
   my $n = @h_input.elems;
   my @h = 0, |@h_input;
   my @ans_coef = berlekamp_massey(@h);
   say @ans_coef.map({ ($^x + MOD) % MOD }).Str;
   my $m = 10;
   my $result = calculate_term($m, @ans_coef, @h);
   say ($result + MOD) % MOD;
}

solve();

```

You may Attempt This Online!