2

I've been doing some research with LFSRs and I have found something I can't explain. I've worked on it for years but I'm finally opening up to public involvement because I can't stand not knowing.

Let's say you have an 8 bit LFSR. As a reminder, it's taps are

76543210
   ^^^ ^

Now, think of the 4 lowest significant bits (bits 3, 2, 1, and 0 above) as a "subregister." For a 4 bit LFSR, the taps are

3210
  ^^

Imagine these 2 LFSRs overlap such that:

Full Register
  vvvvvvvv
  76543210
      ^^^^
Sub Register

Both registers shift to the right. You shift the full register just as you would a normal LFSR. You can "subshift" the sub register by shifting only the bits in the sub register making no changes to the rest of the register. If the sub register contains all 0 bits, it stays all 0s and that counts as the subshift.

With those rules and definitions, I've found that special "intervals" for when to subshift. I've found that for some interval $i$ for a register of $n$ bits that instead of a period of $2^n-1$, it changes to $(2^n-1)*(i+1)$ and during this process, the register will contain every value (except the zero state) $i+1$ times. But ONLY if $i$ is special. Due to it's linear path, starting state doesn't matter as long as $i$ is correct. Also, "every state" means not just the register value, but also how many steps are remaining before the next subshift, i.e. a register value of 4 that is 5 steps away from a subshift is a different state than the register value of 4 that is 2 steps away from a subshift.

If you use a wrong value for $i$, then things go wrong. Some register values will happen multiple times disproportionately and some won't happen at all. Depending on your starting state, it seems that you may find yourself on "disjointed rings." These rings collectively contain every state $i+1$ times. For every value of $i$ it behaves linearly.

Through brute force, I've found that there are 20 values: 11, 29, 63, 68, 83, 104, 106, 129, 134, 150, 155, 170, 176, 177, 192, 195, 202, 225, 237, 253. This is an exhaustive list for an 8 bit LFSR with a 4 bit sub register as described above. In the mean time I've been calling it a SubShifting LFSR or SSLFSR for short. I've also brute forced 16 bit with an 8 bit sub register and found thousands of "working" intervals for it.

The big questions I've been trying to answer for 7 years or so are 1) What makes these intervals special? and 2) Without brute forcing, how can I determine if an interval will work or not (e.g. if I have a 4096 bit SSLFSR, it would take many years to test a single interval and you might find out it didn't work)?

I have a blog post that links to some more resources if I haven't mentioned enough here. I'm not really a technical writer so the writing may be too comfortable or conversational. The two worthwhile links are near the bottom. One is of a PDF where I'm trying to be as clear and technical as I can be, the other is a link to a bitbucket repository with a simple SSLFSR library I've put together.

achille hui
  • 122,701
Corey Ogburn
  • 501
  • If you can make a mathematics question perhaps someone will be interested. Meanwhile, why did you put the tag galois-theory? – Will Jagy Nov 20 '14 at 21:33
  • @WillJagy While talking with some other people about the research, they believed that this type of work is either Ring Theory or Galois Theory because of it's linear behavior. One person tried to model it such that Shifts are movements within a group and subshifts and movements between groups. I think he was the one who called it Galois Theory. To be honest, I'm not 100% sure what domain this belongs in. I'm a software developer without much advanced formal education. I made it as far as Calc 3 before failing. – Corey Ogburn Nov 20 '14 at 21:36
  • Retag under "finite-fields" as the mathematics behind LFSR are primitive polynomials over Galois field (i.e. finite fields). – achille hui Nov 20 '14 at 22:04
  • So, starting with a given state vector $x$, you normally apply the usual shift that (for the purposes of algebra) amounts to applying a certain linear transformation $S$ to $x$. Except that after $i$ rounds you apply a different linear transformatioin $s$. The question seems to be about the order of $sS^i$. I need to think about this one. If the LFSR is of maximal length, then $S$ is simply multiplication by a primitive element of the field, but I don't see right away how to usefully interpret that subshift transformation. Fun question anyway! Have you tried different taps with the subshift? – Jyrki Lahtonen Nov 21 '14 at 15:50
  • @JyrkiLahtonen I have tried a lot of things. I've tried different maximal length taps for the full register and the sub register and found that this affects the list of "working" intervals. I've tried the subregister shifting the opposite direction (LFSRs can move forward or backward as long as you mirror the taps as well) but everything I tried resulted in such random changes that I couldn't follow or predict. I have never tried non-maximal length taps though. That sounds inherently bad for the process. – Corey Ogburn Nov 21 '14 at 15:57

0 Answers0