Shifting an LFSR loop in O(1) time?

I'm wondering if there's a way to combine two concepts: LFSRs, and Barrel Shifters

I'm looking for a way to, in O(1) time, shift an LFSR loop a given number of shifts.

What I'm hoping to find is a simple process where I have the current state of the LFSR and the number of times I want to shift from that state as parameters to a quick/easy process.

At first I just thought about looking at all the taps, then moving the taps over by 1 and looking at them again, finding the shift in bit each time and appending it onto the end but of course this isn't O(1) and it gets complicated if I want to shift so many times that a tap would "slide开发者_Go百科 off" the original LFSR state.

If not in O(1) time, is there a more efficient way to do multiple shifts than doing each one individually?

In general, I am inclined to say that the answer is no. The reason is that if such an algorithm existed, then we could compute in O(1) time any given bit in the sequence generated by the LFSR. This seems unlikely to be doable in general.

However, you can do some precomputation to speed things up somewhat. Note that after any fixed number of steps, the state of each cell in the LFSR is a linear combination of bits from the initial state. So, if you precompute the coefficients in this linear combination for each cell for 1 step, 2 steps, 4 steps, 8 steps, etc, then you should be able to jump ahead many steps in a relatively short time. Of course, this will really only give you useful speedup in the "sliding off" cases that you mention before.

What occurs to me is if the taps occupy a small region of the register, that you could use table lookup to do one bit or more than one bit at a time.

Example, if the register is 8 bits numbered left to right 7 to 0, and the taps are bits 0 and 2. The low order 3 bits could fetch the new bit 7 from an 8-entry table.

Similarly, the low order 4 bits could fetch the new 7,6 bits from a 16-entry table. The low order 5 bits could be used to fetch the new bits 7,6,5 from a 32-entry table, and so on.

Just a thought.

Cryptanalysis of LFSR-based encryption algorithms do essentially this, but in reverse (i.e., they solve for the conditions at [current-N] iterations (usually the initial state) rather than [current+N]. They do this (primarily) by creating a set of linear equations, and then solving. I've never tried to rearrange them to go forward instead of back, but offhand it seems like it should be entirely possible (part of the joy of them being linear...)

As such, reading about some of the known attacks on LFSR-based encryption algorithms would probably be helpful/useful.

If you want to step the LFSR sequence by a power of two, it is possible. If you take a maximum length LFSR sequence and split it up into 2^N parts bit by bit (so that the result of interleaving these parts would give you the original sequence), each of these individual sequences is identical to the original with a shift in phase.

So you can essentially double up the sequence of feedback taps and run 2^N LFSRs in parallel (in a register which is 2^N times wider than the original):

#include <iostream>
using namespace ::std;

void
galois1(const unsigned int taps, const unsigned int seed)
{
  unsigned lfsr = seed;
  do {
    cout << ((lfsr & 1) ? '1' : '0');
    lfsr =
      (lfsr >> 1)
      ^ (-(lfsr & 1) & taps);
  } while (lfsr != seed);

  cout << endl;
}

void
galois2(const unsigned int taps, const unsigned int seed)
{
  unsigned lfsr = seed;
  do {
    cout << ((lfsr & 1) ? '1' : '0') << ((lfsr & 2) ? '1' : '0');
    lfsr =
      (lfsr >> 2)
      ^ (-(lfsr & 1) & taps & 0x5555)
      ^ (-(lfsr & 2) & taps & 0xaaaa);
  } while (lfsr != seed);

  cout << endl;
}

int
main(void)
{
  // Original LFSR sequence, x^5 + x^3 + 1:
  //
  // Taps:  1 0 1 0 0
  // Seed:  1 0 0 0 0

  galois1(0x0014, 0x0010);

  // "Double stepped" sequence, interleaved bits:
  //
  // Taps (even):   1   0   1   0   0
  // Taps (odd):  1   0   1   0   0
  // Seed (even):   0   0   1   0   0
  // Seed (odd):  1   1   0   0   0

  galois2(0x330, 0x290);

  return 0;
}

The only tricky part is figuring out the new seeds (and if you find a way to do that without generating the first 2N bits of the sequence, I'd like to know :-)