galois.berlekamp_massey¶

galois.berlekamp_massey(y, output='minimal')¶

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

This function implements the Berlekamp-Massey algorithm.

Parameters

y : galois.FieldArray

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

output : Literal["minimal", "fibonacci", "galois"]

The output object type.

• "minimal" (default): Returns the minimal polynomial that generates the linear recurrent sequence. The minimal polynomial is the 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.

Return type

galois.Poly or galois.FLFSR or galois.GLFSR

Notes

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

\[\begin{split}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}\end{split}\]

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

References

• Gardner, David. 2019. “Applications of the Galois Model LFSR in Cryptography”. figshare. https://hdl.handle.net/2134/21932.

• Sachs, Jason. 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 \(\mathrm{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 + 3x + 5\) over \(\mathrm{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 and Galois LFSRs that reproduce the sequence.

Fibonacci LFSR

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

Galois LFSR

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