A Fibonacci linear-feedback shift register (LFSR).

Notes¶

A Fibonacci 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 Fibonacci LFSR.

 +--------------+<-------------+<-------------+<-------------+
 |              ^              ^              ^              |
 |              | c_n-1        | c_n-2        | c_1          | c_0
 |              | T[0]         | T[1]         | T[n-2]       | T[n-1]
 |  +--------+  |  +--------+  |              |  +--------+  |
 +->|  S[0]  |--+->|  S[1]  |--+---  ...   ---+->| S[n-1] |--+--> y[t]
    +--------+     +--------+                    +--------+
     y[t+n-1]       y[t+n-2]                       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 Fibonacci configuration, the shift register taps are \(T = [c_{n-1}, c_{n-2}, \dots, c_1, c_0]\). Additionally, the state vector is equal to the next \(n\) outputs in reversed order, namely \(S = [y_{t+n-1}, y_{t+n-2}, \dots, y_{t+2}, y_{t+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.FLFSR(c.reverse())

In [3]: print(lfsr)
Fibonacci LFSR:
  field: GF(2)
  feedback_poly: x^4 + x^3 + 1
  characteristic_poly: x^4 + x + 1
  taps: [0, 0, 1, 1]
  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, 1, 0, 0, 0, 1, 0, 0], order=2)

In [6]: lfsr.state
Out[6]: GF([1, 0, 1, 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.FLFSR(c.reverse())

In [9]: 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: [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, 1, 1, 5, 5, 1, 3, 1, 4], order=7)

In [12]: lfsr.state
Out[12]: GF([5, 5, 6, 6], 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.FLFSR(c.reverse())

In [15]: print(lfsr)
Fibonacci LFSR:
  field: GF(2^3)
  feedback_poly: 3x^4 + x^3 + 1
  characteristic_poly: x^4 + x + 3
  taps: [0, 0, 1, 3]
  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, 1, 2, 2, 2, 1, 4, 4], order=2^3)

In [18]: lfsr.state
Out[18]: GF([0, 3, 7, 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.FLFSR(c.reverse())

In [21]: print(lfsr)
Fibonacci LFSR:
  field: GF(3^3)
  feedback_poly: 10x^4 + x^3 + 1
  characteristic_poly: x^4 + x + 10
  taps: [ 0,  0,  2, 20]
  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,  1, 19, 19, 19,  1, 25, 25], order=3^3)

In [24]: lfsr.state
Out[24]: GF([ 6, 24,  4, 16], order=3^3)

Constructors¶

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

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

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

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

String representation¶

__repr__() → str

A terse representation of the Fibonacci LFSR.

__str__() → str

A formatted string of relevant properties of the Fibonacci LFSR.

Methods¶

reset(state: ArrayLike | None = None)

Resets the Fibonacci LFSR state to the specified state.

step(steps: int = 1) → FieldArray

Produces the next steps output symbols.

to_galois_lfsr() → GLFSR

Converts the Fibonacci LFSR to a Galois 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_{n-1}, c_{n-2}, \dots, c_1, c_0]\). The taps of the shift register define the linear recurrence relation.