<p>We want an algorithm for the following task:</p>
<blockquote>
<p>We are given <span class="math-container">$n$</span> and <span class="math-container">$i$</span> and we want to check if an <span class="math-container">$n$</span>-bit <a href="http://en.wikipedia.org/wiki/LFSR" rel="nofollow noreferrer">LFSR</a> with the sub-register exactly <span class="math-container">$n/2$</span> and an interval of <span class="math-container">$i$</span> &quot;works&quot;. We say an interval of <span class="math-container">$i$</span> &quot;works&quot; when each string <span class="math-container">$x\in \{0,1\}^n$</span> that is not the all-zero string appears exactly <span class="math-container">$i+1$</span> times before the LFSR loops.</p>
</blockquote>
<p>One way of solving the problem is brute-force simulation. Is there a better way of solving this problem?</p>
<hr />
<h3>Background</h3>
<p>So, first a quick refresher on what an LFSR is. A Linear Feedback Shift Register uses particular bits of the current state to help determine what the next state is. By XORing together particular bits (called taps), then shifting the result of the XOR into the register, every value for that size register is achieved once and only once with the only exception being the zero state (where all bits are zero) in which no matter which bits you XOR, you'll shift in another zero. For example, an LFSR with 8 bits will go through all 255 unique states before landing on the original state.</p>
<p><img src="https://i.sstatic.net/AMgud.gif" alt="enter image description here" /></p>
<p>More detailed definitions and examples of LFSRs can be found on <a href="http://en.wikipedia.org/wiki/LFSR" rel="nofollow noreferrer">Wikipedia</a>.</p>
<p>Now assume that we have two LFSRs, one inside the other, e.g. in the picture above assume that the 2 bits on the right hand side are themselves a smaller LFSR. We alternate between performing shift operation on the larger LFSR and on the smaller one. We call the number of times that we shift the larger LFSR before shifting the smaller one the <em>interval</em>.</p>
<hr />
<h3>Motivation</h3>
<p>I began looking for ways to expand on LFSRs, ways to use it or ways to manipulate the process in the name of cryptography. Soon enough I found this interesting reaction. The best way I can think to explain it is through example. P.S. If I say &quot;every state,&quot; assume that I do mean with the exception of the all zero state unless otherwise mentioned.</p>
<p>If you have an 8 bit LFSR, you'll land on every state exactly once before you land on the original starting state. Inspired by how <a href="http://en.wikipedia.org/wiki/A5/1" rel="nofollow noreferrer">A5/1</a> uses multiple LFSRs, I wondered if there was a way I could have 2 LFSRs overlap each other somehow. I began looking into what would happen if an  LFSR &quot;contained&quot; another LFSR. Imagine having an 8 bit LFSR as such:</p>
<pre><code>XXXXYYYY
</code></pre>
<p>Imagine the front half, the 4 Ys, is a second 4 bit LFSR. I started by shifting the entire register (all Xs and Ys above) as an 8 bit LFSR, then shifting the 4 bits (the Ys) before shifting the 8 bits again. It would alternate between shifting all 8, the first 4, all 8, the first 4, etc... I'm inventing terminology here, let's call shifting all 8 bits a &quot;shift&quot; and shifting the first 4 bits as a &quot;subshift.&quot; Note that both shifting and subshifting shift towards the least significant bit to the right. Also, during a subshift, the Xs above are unaffected, the carry bit from the subshift goes in the most significant bit of the sub-register which is the left most Y above.</p>
<p>I wrote a little app with 255 labels to print how often that particular state was landed on. I.e. the 5th label showed how many times the full register held the value 5. The zero label was of course always zero. This yielded nothing initially. Eventually I thought that I was subshifting too often. So I tried shifting twice before subshifting. Then three times... Four... Five... Finally I tried doing 11 shifts between each subshift. That's when the magic happened! I watched as my app slowly totaled up every state to 12. I ran it again, I debugged and stepped through it to make sure I wasn't doing something wrong. If you shift an 8 bit register 11 times, then 1 subshift, then 11 more subshifts, etc. you eventually land on every state 12 times.</p>
<p>My first thought was will 12 land on every value 13 times? And I began testing... Most numbers went on way too long. I generally stopped looking when a state happened more than +1 of the interval I was using (if I had an interval of 40, and a value hit 42, I knew that wouldn't produce the same results as 11 did) and slowly a list formed:</p>
<pre><code>8 bit register with 4 bit sub-register working intervals:
11, 29, 63, 68, 83, 104, 106, 129, 134, 150, 155, 170, 176, 177, 192, 195, 202,
225, 237, 253
</code></pre>
<p>If you shift X number of times, every state will be landed on X + 1 times, BUT only if X (the interval) is one of those values. The only exception to the &quot;+1&quot; trend was 254 which landed on every state 21 times. There's no need to test values larger than 255 (for an 8 bit register), because if you shift 255 times, you'll be back where you started. Remember, these are my findings for 8 bit registers in which the front 4 bits are subshifted.</p>
<p>I looked into doing a 16 bit register with an 8 bit sub-register and began finding equal results (just different values), this is not a complete list because it generally took 6-8 hours to test an interval:</p>
<pre><code>16 bit register with 8 bit sub-register working intervals:
7, 66, 99, 143, 259, 316, 396, 436, 461, 507, 510, 519, 537, 544, 608, 630, 655,
721, 725, 808, 860, 867, 893
</code></pre>
<p>All of these numbers also follow the &quot;+1&quot; rule of each state being landed on <code>interval</code> + 1 times. I understand where the +1 is coming from: if you subshift to a number, you land on that number then shift <code>interval</code> times to <code>interval</code> other numbers.</p>
<p>I've been studying this phenomenon for over a year. My goal is to accurately predict what intervals &quot;work&quot; and which ones don't. Currently my best bet is to brute force (although I know a few things that can indicate early on if an interval DOESN'T work, such as if you land on the initial state it indicates you've made a full cycle.)</p>
<p>Has anybody seen anything like this? Know what kinds of math I can use to analyze and test this with? I've tried using previous working values to predict future values, but they appear to be random, i.e. 29 to 63 is a huge gap where 176 and 177 both work. I've looked into there being a correlation between 8 bit and 16 bit numbers, but since both sets are increasing, they look highly correlated but have a huge standard error. I need to abstractly find what intervals work with 100% accuracy because my encryption requires we finding a working interval for a 4096 bit register... 16 bit took 6 to 8 hours to test a number, 4096 would take billions of billions of years to test a single interval value by brute force.</p>
<p>P.S. I have no clue how to tag this question... Any help would be appreciated there, too.</p>
<p><strong>EDIT:</strong>
Many comments have pointed out I should do smaller register sizes. Here's some of that data in as close to a table as I can get:</p>
<pre><code> 4 bit: 1, 7, 11, 13

 8 bit: 11, 29, 63, 68, 83, 104, 106, 129, 134, 150, 155, 170, 176, 177, 192, 195, 202,
        225, 237, 253

16 bit: 7, 66, 99, 143, 259, 316, 396, 436, 461, 507, 510, 519, 537, 544, 608, 630,
        655, 721, 725, 808, 860, 867, 893
</code></pre>
<p>Because this is more collaborative than Stack Exchange questions usually allow, I'm breaking my rule and putting out my email:</p>
<p><img src="https://i.sstatic.net/Gugae.png" alt="my email" /></p>

CC BY-SA 3.0
2011-08-10T22:49:14.657Z
No, the cycling length of an n-bit LFSR with the sub register being exactly n/2 and an interval of i is ((2^n)-1)*(i+1). I'm asking for how to determine, without brute force, what intervals work. Intervals that "don't work" exhibit very non-uniform behavior.
Corey Ogburn
CC BY-SA 3.0
2011-08-10T22:54:39.437Z
have you solved this for the obvious simpler cases? I.e. 4 bits with the first 2 being subshifted, or even 3 bits with the first 2 being subshifted? Also... your question has a lot of extra text and requires a lot of reading to get at your question. It might be a good idea to follow Dijkstra's advice: "if you can spend 10 minutes to save each of your readers 1 minute, then it is polite to do so if you expect at least 10 readers". At least introduce some headings and clearly mark your question.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-10T22:56:52.243Z
I haven't looked into 4 bit LFSRs with 2 bit sub registers. As for 3 bit LFSRs, I'm not sure whether to round up or down when cutting that in half, I've stuck with 8 and 16 with half size internal registers.
Corey Ogburn
CC BY-SA 3.0
2011-08-10T22:59:17.967Z
you can't round down for 3, since shifting 1 bit is pointless. I strongly suggest solving these simpler 3-2 and 4-2 cases, it will be a good exercise.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-10T23:28:31.700Z
@Corey Ogburn: 1. I agree with Artem, you should edit the question. Move the motivation/background part to the end and separate it from the question. Check the FAQ for more tips about how to write a good question. 2. I still have trouble understnading the question, so the question is: *we are given n and i and we want to check if an n-bit LFSR with the sub-register exactly n/2 and an interval of i "works"*? What do you mean by "works"?
Kaveh
CC BY-SA 3.0
2011-08-10T23:35:19.700Z
@Kaveh I think by "works" he means each string $x \in \{0,1\}^n$ that is not the all-zero string appears exactly $i + 1$ times before the LFSR loops.
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-11T00:04:09.913Z
Artem, you stated exactly what I mean. Kaveh, go ahead. After you do, I'll post my findings for a 4 bit LFSR with a 2 bit sub-register.
Corey Ogburn
CC BY-SA 3.0
2011-08-11T00:17:51.457Z
The interval is new, it's not on wikipedia. As for bringing the data into a table, it's rough the group the data, but a central place would be a good idea.
Corey Ogburn
CC BY-SA 3.0
2011-08-11T01:13:22.167Z
I'm pretty sure this is something brand new about LFSRs and thus not something that can just be looked up or researched. I know this isn't always the place for people working together. But I think a community like this stands the best chance at helping me.
Corey Ogburn
CC BY-SA 3.0
2011-08-11T01:13:54.897Z
@Kaveh let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1049/discussion-between-corey-ogburn-and-kaveh)
Corey Ogburn
CC BY-SA 3.0
2011-08-11T08:20:21.597Z
Here is my simplistic understanding of the problem you are trying to solve that may shed some light on what you are asking for the other people reading it. For an LFSR there is a period $P$ in which it repeats. This is established fact. Now by shifting half the register every interval $I$ then $P$ is multiplied by that much **if $I$ is a particular interval that works**. In addition to that when an interval works it will hit every state exactly $I + 1$ times. The problem is if you try test this on different sized registers we basically get a numbers explosion and running in using a program for
WaffleTop
CC BY-SA 3.0
2011-08-11T18:37:49.880Z
I feel that this post contains an interesting question, but it is too hard to follow it (even though I knew what LFSRs are, but I admit that I am not very familiar with them).  Maybe later….
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-21T03:55:33.650Z
When you mention mixing 2 LFSRs, it reminds me of the [Gold code](http://en.wikipedia.org/wiki/Gold_code) used in most (all?) CDMA cell phone systems, which is formed by mixing 2 LFSRs.
David Cary
CC BY-SA 3.0
2015-11-17T09:24:19.270Z
This question needs to be re-edited and made clear if anyone is expected to seriously consider it. To begin with, you seem to be only considering primitive LFSRs with maximal period $2^n-1$ where $n$ is the length of the register, but even this is not mentioned.
kodlu
CC BY-SA 4.0
2018-06-07T05:11:26.440Z
The Alternating Step Generator invented by Gunther in 1987 does almost exactly what you are looking to do with LFSR's . It "mixes" two LFSR's by XOR'ing them together, but they are randomly clocked into the XOR gate by a third LFSR which is non linear, so the output of the generator is a non linear mixture of the two initial LFSR's. This generator is conjectured to be cryptographically secure.
William Hird
<ds.algorithms><reference-request><co.combinatorics><pseudorandomness>
Expanded use of an LFSR?
Corey Ogburn
# Expanded use of an LFSR?

(Asked by: username_0 on 2011-08-10)

We want an algorithm for the following task:

We are given $n$ and $i$ and we want to check if an $n$-bit LFSR with the sub-register exactly $n/2$ and an interval of $i$ "works". We say an interval of $i$ "works" when each string $x\in \{0,1\}^n$ that is not the all-zero string appears exactly $i+1$ times before the LFSR loops.

One way of solving the problem is brute-force simulation. Is there a better way of solving this problem?

Background
So, first a quick refresher on what an LFSR is. A Linear Feedback Shift Register uses particular bits of the current state to help determine what the next state is. By XORing together particular bits (called taps), then shifting the result of the XOR into the register, every value for that size register is achieved once and only once with the only exception being the zero state (where all bits are zero) in which no matter which bits you XOR, you'll shift in another zero. For example, an LFSR with 8 bits will go through all 255 unique states before landing on the original state.

More detailed definitions and examples of LFSRs can be found on Wikipedia.
Now assume that we have two LFSRs, one inside the other, e.g. in the picture above assume that the 2 bits on the right hand side are themselves a smaller LFSR. We alternate between performing shift operation on the larger LFSR and on the smaller one. We call the number of times that we shift the larger LFSR before shifting the smaller one the interval.

Motivation
I began looking for ways to expand on LFSRs, ways to use it or ways to manipulate the process in the name of cryptography. Soon enough I found this interesting reaction. The best way I can think to explain it is through example. P.S. If I say "every state," assume that I do mean with the exception of the all zero state unless otherwise mentioned.
If you have an 8 bit LFSR, you'll land on every state exactly once before you land on the original starting state. Inspired by how A5/1 uses multiple LFSRs, I wondered if there was a way I could have 2 LFSRs overlap each other somehow. I began looking into what would happen if an  LFSR "contained" another LFSR. Imagine having an 8 bit LFSR as such:
XXXXYYYY

Imagine the front half, the 4 Ys, is a second 4 bit LFSR. I started by shifting the entire register (all Xs and Ys above) as an 8 bit LFSR, then shifting the 4 bits (the Ys) before shifting the 8 bits again. It would alternate between shifting all 8, the first 4, all 8, the first 4, etc... I'm inventing terminology here, let's call shifting all 8 bits a "shift" and shifting the first 4 bits as a "subshift." Note that both shifting and subshifting shift towards the least significant bit to the right. Also, during a subshift, the Xs above are unaffected, the carry bit from the subshift goes in the most significant bit of the sub-register which is the left most Y above.
I wrote a little app with 255 labels to print how often that particular state was landed on. I.e. the 5th label showed how many times the full register held the value 5. The zero label was of course always zero. This yielded nothing initially. Eventually I thought that I was subshifting too often. So I tried shifting twice before subshifting. Then three times... Four... Five... Finally I tried doing 11 shifts between each subshift. That's when the magic happened! I watched as my app slowly totaled up every state to 12. I ran it again, I debugged and stepped through it to make sure I wasn't doing something wrong. If you shift an 8 bit register 11 times, then 1 subshift, then 11 more subshifts, etc. you eventually land on every state 12 times.
My first thought was will 12 land on every value 13 times? And I began testing... Most numbers went on way too long. I generally stopped looking when a state happened more than +1 of the interval I was using (if I had an interval of 40, and a value hit 42, I knew that wouldn't produce the same results as 11 did) and slowly a list formed:
8 bit register with 4 bit sub-register working intervals:
11, 29, 63, 68, 83, 104, 106, 129, 134, 150, 155, 170, 176, 177, 192, 195, 202,
225, 237, 253

If you shift X number of times, every state will be landed on X + 1 times, BUT only if X (the interval) is one of those values. The only exception to the "+1" trend was 254 which landed on every state 21 times. There's no need to test values larger than 255 (for an 8 bit register), because if you shift 255 times, you'll be back where you started. Remember, these are my findings for 8 bit registers in which the front 4 bits are subshifted.
I looked into doing a 16 bit register with an 8 bit sub-register and began finding equal results (just different values), this is not a complete list because it generally took 6-8 hours to test an interval:
16 bit register with 8 bit sub-register working intervals:
7, 66, 99, 143, 259, 316, 396, 436, 461, 507, 510, 519, 537, 544, 608, 630, 655,
721, 725, 808, 860, 867, 893

All of these numbers also follow the "+1" rule of each state being landed on interval + 1 times. I understand where the +1 is coming from: if you subshift to a number, you land on that number then shift interval times to interval other numbers.
I've been studying this phenomenon for over a year. My goal is to accurately predict what intervals "work" and which ones don't. Currently my best bet is to brute force (although I know a few things that can indicate early on if an interval DOESN'T work, such as if you land on the initial state it indicates you've made a full cycle.)
Has anybody seen anything like this? Know what kinds of math I can use to analyze and test this with? I've tried using previous working values to predict future values, but they appear to be random, i.e. 29 to 63 is a huge gap where 176 and 177 both work. I've looked into there being a correlation between 8 bit and 16 bit numbers, but since both sets are increasing, they look highly correlated but have a huge standard error. I need to abstractly find what intervals work with 100% accuracy because my encryption requires we finding a working interval for a 4096 bit register... 16 bit took 6 to 8 hours to test a number, 4096 would take billions of billions of years to test a single interval value by brute force.
P.S. I have no clue how to tag this question... Any help would be appreciated there, too.
EDIT:
Many comments have pointed out I should do smaller register sizes. Here's some of that data in as close to a table as I can get:
 4 bit: 1, 7, 11, 13

 8 bit: 11, 29, 63, 68, 83, 104, 106, 129, 134, 150, 155, 170, 176, 177, 192, 195, 202,
        225, 237, 253

16 bit: 7, 66, 99, 143, 259, 316, 396, 436, 461, 507, 510, 519, 537, 544, 608, 630,
        655, 721, 725, 808, 860, 867, 893

Because this is more collaborative than Stack Exchange questions usually allow, I'm breaking my rule and putting out my email:

**Tags:** ds.algorithms, reference-request, co.combinatorics, pseudorandomness
> **Comments:**
> **username_0**: No, the cycling length of an n-bit LFSR with the sub register being exactly n/2 and an interval of i is ((2^n)-1)*(i+1). I'm asking for how to determine, without brute force, what intervals work. Intervals that "don't work" exhibit very non-uniform behavior.  
> **username_1**: have you solved this for the obvious simpler cases? I.e. 4 bits with the first 2 being subshifted, or even 3 bits with the first 2 being subshifted? Also... your question has a lot of extra text and requires a lot of reading to get at your question. It might be a good idea to follow Dijkstra's advice: "if you can spend 10 minutes to save each of your readers 1 minute, then it is polite to do so if you expect at least 10 readers". At least introduce some headings and clearly mark your question.  
> **username_0**: I haven't looked into 4 bit LFSRs with 2 bit sub registers. As for 3 bit LFSRs, I'm not sure whether to round up or down when cutting that in half, I've stuck with 8 and 16 with half size internal registers.  
> **username_1**: you can't round down for 3, since shifting 1 bit is pointless. I strongly suggest solving these simpler 3-2 and 4-2 cases, it will be a good exercise.  
> **username_2**: @Corey Ogburn: 1. I agree with Artem, you should edit the question. Move the motivation/background part to the end and separate it from the question. Check the FAQ for more tips about how to write a good question. 2. I still have trouble understnading the question, so the question is: *we are given n and i and we want to check if an n-bit LFSR with the sub-register exactly n/2 and an interval of i "works"*? What do you mean by "works"?  
> **username_1**: @Kaveh I think by "works" he means each string $x \in \{0,1\}^n$ that is not the all-zero string appears exactly $i + 1$ times before the LFSR loops.  
> **username_0**: Artem, you stated exactly what I mean. Kaveh, go ahead. After you do, I'll post my findings for a 4 bit LFSR with a 2 bit sub-register.  
> **username_0**: The interval is new, it's not on wikipedia. As for bringing the data into a table, it's rough the group the data, but a central place would be a good idea.  
> **username_0**: I'm pretty sure this is something brand new about LFSRs and thus not something that can just be looked up or researched. I know this isn't always the place for people working together. But I think a community like this stands the best chance at helping me.  
> **username_0**: @Kaveh let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/1049/discussion-between-corey-ogburn-and-kaveh)  
> **username_3**: Here is my simplistic understanding of the problem you are trying to solve that may shed some light on what you are asking for the other people reading it. For an LFSR there is a period $P$ in which it repeats. This is established fact. Now by shifting half the register every interval $I$ then $P$ is multiplied by that much **if $I$ is a particular interval that works**. In addition to that when an interval works it will hit every state exactly $I + 1$ times. The problem is if you try test this on different sized registers we basically get a numbers explosion and running in using a program for  
> **username_4**: I feel that this post contains an interesting question, but it is too hard to follow it (even though I knew what LFSRs are, but I admit that I am not very familiar with them).  Maybe later….  
> **username_5**: When you mention mixing 2 LFSRs, it reminds me of the [Gold code](http://en.wikipedia.org/wiki/Gold_code) used in most (all?) CDMA cell phone systems, which is formed by mixing 2 LFSRs.  
> **username_6**: This question needs to be re-edited and made clear if anyone is expected to seriously consider it. To begin with, you seem to be only considering primitive LFSRs with maximal period $2^n-1$ where $n$ is the length of the register, but even this is not mentioned.  
> **username_7**: The Alternating Step Generator invented by Gunther in 1987 does almost exactly what you are looking to do with LFSR's . It "mixes" two LFSR's by XOR'ing them together, but they are randomly clocked into the XOR gate by a third LFSR which is non linear, so the output of the generator is a non linear mixture of the two initial LFSR's. This generator is conjectured to be cryptographically secure.  

---

## 0 answers

