galois.berlekamp_massey

galois.berlekamp_massey(sequence: FieldArray, output: 'minimal' = 'minimal') → Poly

galois.berlekamp_massey(sequence: FieldArray, output: 'fibonacci') → FLFSR

galois.berlekamp_massey(sequence: FieldArray, output: 'galois') → GLFSR

Finds the minimal polynomial $c (x)$ that produces the linear recurrent sequence $y$ .

This function implements the Berlekamp-Massey algorithm.

Parameters:¶

sequence: FieldArray¶

A linear recurrent sequence $y$ in $GF (p^{m})$ .

output: 'minimal' = 'minimal'¶

output: 'fibonacci'

output: 'galois'

The output object type.

"minimal" (default): Returns the minimal polynomial that generates the linear recurrent sequence. The minimal polynomial is a characteristic polynomial $c (x)$ of minimal degree.
"fibonacci": Returns a Fibonacci LFSR that produces $y$ .
"galois": Returns a Galois LFSR that produces $y$ .

Returns:¶

The minimal polynomial $c (x)$ , a Fibonacci LFSR, or a Galois LFSR, depending on the value of output.

Notes¶

The minimal polynomial is the characteristic polynomial $c (x)$ of minimal degree that produces the linear recurrent sequence $y$ .

c (x) = x^{n} - c_{n - 1} x^{n - 1} - c_{n - 2} x^{n - 2} - \dots - c_{1} x - c_{0}

y_{t} = c_{n - 1} y_{t - 1} + c_{n - 2} y_{t - 2} + \dots + c_{1} y_{t - n + 2} + c_{0} y_{t - n + 1}

For a linear sequence with order $n$ , at least $2 n$ output symbols are required to determine the minimal polynomial.

References¶

Gardner, D. 2019. “Applications of the Galois Model LFSR in Cryptography”. https://hdl.handle.net/2134/21932.
Sachs, J. Linear Feedback Shift Registers for the Uninitiated, Part VI: Sing Along with the Berlekamp-Massey Algorithm. https://www.embeddedrelated.com/showarticle/1099.php
https://crypto.stanford.edu/~mironov/cs359/massey.pdf

Examples¶

The sequence below is a degree-4 linear recurrent sequence over $GF (7)$ .

In [1]: GF = galois.GF(7)

In [2]: y = GF([5, 5, 1, 3, 1, 4, 6, 6, 5, 5])

The characteristic polynomial is $c (x) = x^{4} + x^{2} + 3 x + 5$ over $GF (7)$ .

In [3]: galois.berlekamp_massey(y)
Out[3]: Poly(x^4 + x^2 + 3x + 5, GF(7))

Use the Berlekamp-Massey algorithm to return equivalent Fibonacci LFSR that reproduces the sequence.

In [4]: lfsr = galois.berlekamp_massey(y, output="fibonacci")

In [5]: print(lfsr)
Fibonacci LFSR:
  field: GF(7)
  feedback_poly: 5x^4 + 3x^3 + x^2 + 1
  characteristic_poly: x^4 + x^2 + 3x + 5
  taps: [0 6 4 2]
  order: 4
  state: [3 1 5 5]
  initial_state: [3 1 5 5]

In [6]: z = lfsr.step(y.size); z
Out[6]: GF([5, 5, 1, 3, 1, 4, 6, 6, 5, 5], order=7)

In [7]: np.array_equal(y, z)
Out[7]: True

Use the Berlekamp-Massey algorithm to return equivalent Galois LFSR that reproduces the sequence.

In [8]: lfsr = galois.berlekamp_massey(y, output="galois")

In [9]: print(lfsr)
Galois LFSR:
  field: GF(7)
  feedback_poly: 5x^4 + 3x^3 + x^2 + 1
  characteristic_poly: x^4 + x^2 + 3x + 5
  taps: [2 4 6 0]
  order: 4
  state: [2 6 5 5]
  initial_state: [2 6 5 5]

In [10]: z = lfsr.step(y.size); z
Out[10]: GF([5, 5, 1, 3, 1, 4, 6, 6, 5, 5], order=7)

In [11]: np.array_equal(y, z)
Out[11]: True