This Mathematica package provides a symbolic representation of Linear Feedback Shift Registers, often used in cryptography. With this package, you can generate bit sequences from LFSRs, and from bit sequences determine the minimal generating LFSR along with the linear complexity profile using the Berlekamp-Massey Algorithm.

Linear Feedback Shift Registers (LFSR) are primarly used in cryptography and random number testing. More information on them can be found in Applied Cryptography or Handbook of Applied Cryptography. More on the Berlekamp-Massey algorithm can be found at MathWorld.

Examples

LFSR[complexity, polynomial] is an abstract Linear Feedback Shift Register. By itself it doesn't do anything.

``` <lfsr x = LFSR[4, 1 + t + t^4]

LFSR[4, 1 + t + t^4]

```

LFSRGenerate generates bits from an LFSR given an initial state. When an explicit list `is passed in, the end state of the LFSR is not saved, and the sequence can not be restarted.

``` (* generate 11 bits from x, with an initial state *) result1 = LFSRGenerate[x, 11, {0, 1, 1, 0}]

{0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1}

```

However if you pass in a symbol for the state, the symbol will be updated with the current state of the LFSR. This should allow one to construct banks of different LFSRs.

``` (* put state in a symbol *) state = {0, 1, 1, 0};

(* generate sequence in 2 steps *) result2 = Flatten[{LFSRGenerate[x, 6, state], LFSRGenerate[x, 5, state]}] {0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1}

state {1, 1, 0, 1} (* new state *)

```

LinearComplexityProfile is the "reverse" operation of LFSRGenerate: Given a sequence of bits, it computes the smallest LFSR that can generate the sequence. This is done using the Berlekamp-Massey algorithm. It also provides the "profile" -- the complexity at each position in sequence.

``` LinearComplexityProfile[result2, t] // InputForm

{LFSR[4, 1 + t + t^4], {0, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4}}

```

If you just want the linear complexity of sequence, the function LinearComplexity is at least 10x faster than using LinearComplexityProfile (it uses a different, compiled implementation)

LinearComplexity[result] 4

Meta Data

ChangeLog

• 01-Jul-2007: Add to googlecode
• 23-Aug-2005: 2.0.0 10x+ improvement with LinearComplexity
• 07-Apr-2005: 1.1.0: Name space cleanup
• 01-Feb-2005: 1.0.0: Initial release

To Do

This package was primarly designed for the Berlekamp-Massey algorithm, and the LFSRGenerate was written mostly for testing. For people developing stream-ciphers or other applications of LFSRs, it might be more useful to put the state in the LFSR object itself: LFSR[complexity, polynomial, state]. Feedback welcome (pun intended) on which implementation is better.