As it is a linear system, it appears you can decompose the state into a set of bits, have precalced values for those bits advanced through N states, and then recombine them.
So you could have precanceled values for advancing the LFSR through 2^24 bits, and through 2^12 bits, and of course, one bit. You can then take a 36-bit LFSR through to any state in at most 2 ^12 * 3 operations, rather than 2^36-1 operations,
With 36 sets of precalculated values (first set to advance through 1 state, second to advance through 2 states, advance through 4 states, ... advance through 2^34 states, advance through 2^35 states), you move through any number of states in 36 decompose-lookup-merge operations.
Calculating these is table values relatively simple. Calculate the first set, use them twice to calculate the second set. Use them twice to calculate next set, and so on.
The code below is a maximal 5-bit XNOR LFSR, and calculates four states ahead.
#include <stdio.h>
#include <stdint.h>
uint32_t advance_lfsr(uint32_t state) {
uint32_t new_bit;
new_bit = 1^((state & 0x10) ? 1 : 0) ^ ((state & 0x02) ? 1 : 0);
state = (state << 1 )|new_bit;
state &= 0x1f;
return state;
}
int main(int argc, char *argv[])
{
uint32_t initial = 0x00;
uint32_t state = initial;
printf("Calculated and guessed are the LFSR advanced by 4 states\n");
printf("\n");
printf("State Calculated Guessed Error?\n");
do {
uint32_t guess, calced, i;
guess = 0x0c;
if((state & 0x01) != 0) guess ^= 0x19 ^ 0x0C;
if((state & 0x02) != 0) guess ^= 0x07 ^ 0x0C;
if((state & 0x04) != 0) guess ^= 0x0e ^ 0x0C;
if((state & 0x08) != 0) guess ^= 0x09 ^ 0x0C;
if((state & 0x10) != 0) guess ^= 0x06 ^ 0x0C;
calced = state;
for(i = 0; i < 4; i++) {
calced = advance_lfsr(calced);
}
printf("%02x %02x %02x %s\n", state, calced, guess, calced ^ guess ? "yes" : "no");
state = advance_lfsr(state);
} while(state != initial);
return 0;
}
And the results:
Calculated and guessed are the LFSR advanced by 4 states
State Calculated Guessed Error?
00 0c 0c no
01 19 19 no
03 12 12 no
06 05 05 no
0c 0b 0b no
19 16 16 no
12 0d 0d no
05 1b 1b no
0b 17 17 no
16 0f 0f no
0d 1e 1e no
1b 1d 1d no
17 1a 1a no
0f 15 15 no
1e 0a 0a no
1d 14 14 no
1a 08 08 no
15 11 11 no
0a 02 02 no
14 04 04 no
08 09 09 no
11 13 13 no
02 07 07 no
04 0e 0e no
09 1c 1c no
13 18 18 no
07 10 10 no
0e 00 00 no
1c 01 01 no
18 03 03 no
10 06 06 no
Why would you be needing to do this?
(Oh the key point I missed is that going forward by four states is the same as going backwards by (2^n-1)-4 states).