galois.GLFSR¶

class galois.GLFSR(feedback_poly: Poly, state: ArrayLike | None = None)¶

A Galois linear-feedback shift register (LFSR).

Notes

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

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

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

\[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}\]

Galois LFSR Configuration¶

 +--------------+<-------------+<-------------+<-------------+
 |              |              |              |              |
 | 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.

See also

berlekamp_massey

Examples

GF(2)

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(2)\).

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]

Step the Galois LFSR and produce 10 output symbols.

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)

GF(p)

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(7)\).

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]

Step the Galois LFSR and produce 10 output symbols.

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)

GF(2^m)

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(2^3)\).

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]

Step the Galois LFSR and produce 10 output symbols.

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)

GF(p^m)

Create a Galois LFSR from a degree-4 primitive characteristic polynomial over \(\mathrm{GF}(3^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]

Step the Galois LFSR and produce 10 output symbols.

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

`__init__`(feedback_poly[, state])	Constructs a Galois LFSR from its feedback polynomial \(f(x)\).
`Taps`(taps[, state])	Constructs a Galois LFSR from its taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

Special Methods

`__repr__`()	A terse representation of the Galois LFSR.
`__str__`()	A formatted string of relevant properties of the Galois LFSR.

Methods

`reset`([state])	Resets the Galois LFSR state to the specified state.
`step`([steps])	Produces the next `steps` output symbols.
`to_fibonacci_lfsr`()	Converts the Galois LFSR to a Fibonacci LFSR that produces the same output.

Attributes

`characteristic_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.
`feedback_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.
`field`	The `FieldArray` subclass for the finite field that defines the linear arithmetic.
`initial_state`	The initial state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).
`order`	The order of the linear recurrence/linear recurrent sequence.
`state`	The current state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\).
`taps`	The shift register taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

__init__(feedback_poly: Poly, state: ArrayLike | None = None)¶

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

Parameters

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\).
state: ArrayLike | None = None¶: The initial state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\). The default is None which corresponds to all ones.

See also

irreducible_poly, primitive_poly

Notes

A Galois LFSR may be constructed from its characteristic polynomial \(c(x)\) by passing in its reciprocal as the feedback polynomial. This is because \(f(x) = x^n c(x^{-1})\).

classmethod Taps(taps: FieldArray, state: ArrayLike | None = None) → GLFSR¶

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

Parameters

taps: FieldArray¶: The shift register taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).
state: ArrayLike | None = None¶: The initial state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\). The default is None which corresponds to all ones.

Returns

A Galois LFSR with taps \(T = [c_0, c_1, \dots, c_{n-2}, c_{n-1}]\).

Examples

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

In [2]: taps = -c.coeffs[1:][::-1]; taps
Out[2]: GF([2, 4, 6, 0], order=7)

In [3]: lfsr = galois.GLFSR.Taps(taps)

In [4]: 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]

__repr__() → str¶

A terse representation of the Galois LFSR.

Examples

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

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

In [3]: lfsr
Out[3]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

__str__() → str¶

A formatted string of relevant properties of the Galois LFSR.

Examples

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

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

In [3]: 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]

reset(state: ArrayLike | None = None)¶

Resets the Galois LFSR state to the specified state.

Parameters

state: ArrayLike | None = None¶: The state vector \(S = [S_0, S_1, \dots, S_{n-2}, S_{n-1}]\). The default is None which corresponds to the initial state.

Examples

Initial state

Step the Galois LFSR 10 steps to modify its state.

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

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

Reset the Galois LFSR state.

In [6]: lfsr.reset()

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

Specific state

Create an Galois LFSR and view its initial state.

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

In [9]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[9]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

Reset the Galois LFSR state to a new state.

In [11]: lfsr.reset([1, 2, 3, 4])

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

step(steps: int = 1) → FieldArray¶

Produces the next steps output symbols.

Negative values may be passed which reverses the direction of the shift registers and produces outputs in reverse order.

Parameters

steps: int = 1¶: The direction and number of output symbols to produce. The default is 1. If negative, the Galois LFSR will step backward.

Returns

An array of output symbols of type field with size abs(steps).

Examples

Scalar output

Step the Galois LFSR one output at a time.

In [1]: c = galois.primitive_poly(7, 4)

In [2]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

In [5]: lfsr.state, lfsr.step()
Out[5]: (GF([6, 6, 0, 5], order=7), GF(5, order=7))

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

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

# Ending state
In [8]: lfsr.state
Out[8]: GF([2, 4, 2, 5], order=7)

Vector output

Step the Galois LFSR 5 steps in one call. This is more efficient than iterating one output at a time. Notice the output and ending state are the same from the Scalar output tab.

In [9]: c = galois.primitive_poly(7, 4)

In [10]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[10]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

# Ending state
In [13]: lfsr.state
Out[13]: GF([2, 4, 2, 5], order=7)

Step backwards

Step the Galois LFSR 10 steps forward.

In [14]: c = galois.primitive_poly(7, 4)

In [15]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[15]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

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

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

Step the Galois LFSR 10 steps backward. Notice the output sequence is the reverse of the original sequence. Also notice the ending state is the same as the initial state.

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

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

to_fibonacci_lfsr() → FLFSR¶

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

Returns: An equivalent Fibonacci LFSR.

Examples

Create a Galois LFSR with a given initial state.

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

In [2]: galois_lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4])

In [3]: print(galois_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, 2, 3, 4]
  initial_state: [1, 2, 3, 4]

Convert the Galois LFSR to an equivalent Fibonacci LFSR. Notice the initial state is different.

In [4]: fibonacci_lfsr = galois_lfsr.to_fibonacci_lfsr()

In [5]: print(fibonacci_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: [0, 5, 3, 4]
  initial_state: [0, 5, 3, 4]

Step both LFSRs and see that their output sequences are identical.

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

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

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})\).

Examples

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [3]: lfsr.characteristic_poly
Out[3]: Poly(x^4 + x^2 + 3x + 5, GF(7))

In [4]: lfsr.characteristic_poly == lfsr.feedback_poly.reverse()
Out[4]: True

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})\).

Examples

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [3]: lfsr.feedback_poly
Out[3]: Poly(5x^4 + 3x^3 + x^2 + 1, GF(7))

In [4]: lfsr.feedback_poly == lfsr.characteristic_poly.reverse()
Out[4]: True

property field : type[FieldArray]¶

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

Examples

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

In [2]: lfsr = galois.GLFSR(c.reverse()); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [3]: lfsr.field
Out[3]: galois.GF(7)

property initial_state : FieldArray¶

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

Examples

In [1]: c = galois.primitive_poly(7, 4)

In [2]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

The initial state is unaffected as the Galois LFSR is stepped.

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

In [5]: lfsr.initial_state
Out[5]: GF([1, 2, 3, 4], order=7)

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}]\).

Examples

In [1]: c = galois.primitive_poly(7, 4)

In [2]: lfsr = galois.GLFSR(c.reverse(), state=[1, 2, 3, 4]); lfsr
Out[2]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

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

The current state is modified as the Galois LFSR is stepped.

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

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

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.

Examples

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

In [2]: taps = -c.coeffs[1:][::-1]; taps
Out[2]: GF([2, 4, 6, 0], order=7)

In [3]: lfsr = galois.GLFSR.Taps(taps); lfsr
Out[3]: <Galois LFSR: f(x) = 5x^4 + 3x^3 + x^2 + 1 over GF(7)>

In [4]: lfsr.taps
Out[4]: GF([2, 4, 6, 0], order=7)

Last update: May 12, 2022