A Galois linear-feedback shift register (LFSR).

Notes¶

A Galois LFSR is defined by its feedback polynomial \(f(x)\).

The feedback polynomial is the reciprocal of the characteristic polynomial \(c(x)\) of the linear recurrent sequence \(y\) produced by the Galois LFSR.

 +--------------+<-------------+<-------------+<-------------+
 |              |              |              |              |
 | c_0          | c_1          | c_2          | c_n-1        |
 | T[0]         | T[1]         | T[2]         | T[n-1]       |
 |  +--------+  v  +--------+  v              v  +--------+  |
 +->|  S[0]  |--+->|  S[1]  |--+---  ...   ---+->| S[n-1] |--+--> y[t]
    +--------+     +--------+                    +--------+
                                                   y[t+1]

The shift register taps \(T\) are defined left-to-right as \(T = [T_0, T_1, \dots, T_{n-2}, T_{n-1}]\). The state vector \(S\) is also defined left-to-right as \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).

In the Galois configuration, the shift register taps are \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

References¶

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

Examples¶

In [1]: c = galois.primitive_poly(2, 4); c
Out[1]: Poly(x^4 + x + 1, GF(2))

In [2]: lfsr = galois.GLFSR(c.reverse())

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

In [4]: lfsr.state
Out[4]: GF([1, 1, 1, 1], order=2)

In [5]: lfsr.step(10)
Out[5]: GF([1, 1, 1, 0, 0, 0, 1, 0, 0, 1], order=2)

In [6]: lfsr.state
Out[6]: GF([1, 1, 0, 1], order=2)

In [7]: c = galois.primitive_poly(7, 4); c
Out[7]: Poly(x^4 + x^2 + 3x + 5, GF(7))

In [8]: lfsr = galois.GLFSR(c.reverse())

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: [1, 1, 1, 1]
  initial_state: [1, 1, 1, 1]

In [10]: lfsr.state
Out[10]: GF([1, 1, 1, 1], order=7)

In [11]: lfsr.step(10)
Out[11]: GF([1, 1, 0, 4, 6, 5, 3, 6, 1, 2], order=7)

In [12]: lfsr.state
Out[12]: GF([4, 3, 0, 1], order=7)

In [13]: c = galois.primitive_poly(2**3, 4); c
Out[13]: Poly(x^4 + x + 3, GF(2^3))

In [14]: lfsr = galois.GLFSR(c.reverse())

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

In [16]: lfsr.state
Out[16]: GF([1, 1, 1, 1], order=2^3)

In [17]: lfsr.step(10)
Out[17]: GF([1, 1, 1, 0, 2, 2, 3, 2, 4, 5], order=2^3)

In [18]: lfsr.state
Out[18]: GF([4, 2, 2, 7], order=2^3)

In [19]: c = galois.primitive_poly(3**3, 4); c
Out[19]: Poly(x^4 + x + 10, GF(3^3))

In [20]: lfsr = galois.GLFSR(c.reverse())

In [21]: print(lfsr)
Galois LFSR:
  field: GF(3^3)
  feedback_poly: 10x^4 + x^3 + 1
  characteristic_poly: x^4 + x + 10
  taps: [20,  2,  0,  0]
  order: 4
  state: [1, 1, 1, 1]
  initial_state: [1, 1, 1, 1]

In [22]: lfsr.state
Out[22]: GF([1, 1, 1, 1], order=3^3)

In [23]: lfsr.step(10)
Out[23]: GF([ 1,  1,  1,  0, 19, 19, 20, 11, 25, 24], order=3^3)

In [24]: lfsr.state
Out[24]: GF([23, 25,  6, 26], order=3^3)

Constructors¶

GLFSR(feedback_poly: Poly, state: ArrayLike | None = None)

Constructs a Galois LFSR from its feedback polynomial \(f(x)\).

classmethod Taps(taps: FieldArray, ...) → GLFSR

Constructs a Galois LFSR from its taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

String representation¶

__repr__() → str

A terse representation of the Galois LFSR.

__str__() → str

A formatted string of relevant properties of the Galois LFSR.

Methods¶

reset(state: ArrayLike | None = None)

Resets the Galois LFSR state to the specified state.

step(steps: int = 1) → FieldArray

Produces the next steps output symbols.

to_fibonacci_lfsr() → FLFSR

Converts the Galois LFSR to a Fibonacci LFSR that produces the same output.

Properties¶

property characteristic_poly : Poly

The characteristic polynomial \(c(x) = x^{n} - c_{n-1}x^{n-1} - c_{n-2}x^{n-2} - \dots - c_{1}x - c_{0}\) that defines the linear recurrent sequence. The characteristic polynomial is the reciprocal of the feedback polynomial \(c(x) = x^n f(x^{-1})\).

property feedback_poly : Poly

The feedback polynomial \(f(x) = -c_{0}x^{n} - c_{1}x^{n-1} - \dots - c_{n-2}x^{2} - c_{n-1}x + 1\) that defines the feedback arithmetic. The feedback polynomial is the reciprocal of the characteristic polynomial \(f(x) = x^n c(x^{-1})\).

property field : Type[FieldArray]

The FieldArray subclass for the finite field that defines the linear arithmetic.

property initial_state : FieldArray

The initial state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).

property order : int

The order of the linear recurrence/linear recurrent sequence. The order of a sequence is defined by the degree of the minimal polynomial that produces it.

property state : FieldArray

The current state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).

property taps : FieldArray

The shift register taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\). The taps of the shift register define the linear recurrence relation.