We’re rewarding the question askers & reputations are being recalculated! Read more.
2 of 4 added 2088 characters in body

LFSR Jump Ahead Algorithm

A related question has been asked and answered here. My question is specifically about figuring out C for very large J. I have searched the web and found many scholarly articles on "jump ahead" and how to efficiently do so, but I am looking for a more "layman's" algorithm.

Here is the background information. I am working through understanding the areas of weakness in using LFSR in cryptography. To proof the concept, I have an encrypted message from a stream cipher using an N-bit LFSR. The plain-text is ASCII, so I know the plain-text bits recurring at a specific interval (8), call it m. From that, I get a set of non-consecutive key bits. I have used the Berlekamp-Massey on the first 128 such bits at index multiples of m, then used the resulting coefficients and the first 64 bits passed to BM to initialize an LFSR. I've run through the rest of the message proving to myself that the bits at multiple m are all predictable.

Now I would like to prove the remaining piece to myself, namely to get back the LFSR coefficients for the message, with only having a subset of the key bits and an associated LFSR for those bits. In the question I made reference to, I am stuck trying to figure out C at i * m^-1 mod p. In other words, this value is too large to just step to that point in the LFSR state. As, I said, I found articles that discuss LFSR "jump ahead", but I think I need something more explicit on the approach.

For instance, the simplest method (and slowest), is to create a matrix Av for each jump ahead value v from the polynomial. Av is K x K. But I find no information on how to create the square matrix from this polynomial. To prove the concept, I don't need a fast algorithm, just something I can apply to close the loop.

An algorithm (Python, C, Java, et al), or implementation would be most helpful. But even an article that give more complete details on the approach could serve the purpose. Can you recommend something?

EDIT

Here is a specific example. Using Fibonacci mode:

Coefficients: [
1, 1, 1, 1, 1, 0, 0, 0,
0, 0, 0, 1, 0, 1, 0, 0,
1, 0, 1, 0, 1, 0, 0, 0,
1, 1, 1, 1, 1, 1, 0, 1,
0, 1, 1, 1, 1, 1, 0, 0,
1, 1, 0, 0, 1, 0, 1, 1,
0, 0, 1, 1, 1, 0, 1, 1,
1, 1, 0, 0, 1, 0, 0, 1 ]
State: [
0, 0, 0, 0, 1, 1, 1, 1,
0, 1, 0, 1, 1, 0, 1, 1,
0, 1, 1, 0, 0, 0, 0, 1,
1, 1, 0, 1, 1, 0, 0, 1,
1, 1, 0, 0, 1, 0, 1, 0,
0, 0, 0, 0, 1, 1, 0, 0,
1, 0, 0, 1, 1, 0, 0, 1,
0, 0, 0, 1, 1, 1, 1, 0
]

The state bits come from the base64 decoded message

QVs7HbrYu4Qg2y3p6lnBsRvYhDlQRgLhh8QItrMVO62YqVpXyl6SEyxrZiSg3nEo7B
g65eFWQ5gfGFTw2ouScd8Q6/NXN6CwZkGc4RkBhUPJ7P7tHeq0y5R0lNYyCXTkU/op
WgyZJBWm4NQoP8h7dtHUlVzUX6Run/cnwkToMwaEHxT2nP8fWQ10FA8KwjuR066TwP
oPfkrVc1S0l+RbKHnfZwxiKYJP3UMckbKJ3utJ1pTZdX3uWj/moFoFGSWnlM28QBCu
JaIVBrPmgItaqaJM2o52b90KMPUr9cxBTPdwCXXp5ViCdhJgv2QuQkTtk5eQgiyGkM
EiM7bl4WqMunscTa3vPA+Fhq0elGJKAe4t1K3ghX3Q44u9A6BTrxjZrTa+Mi73YWGQ
Ehs5G6HRi3hrNYavbBKaFqs56/R/6wd2QsFVSSno/NyAKKuUk5EFUQVL2uwfCpxn2F
QeRRZ2Ok8Leo6B/Fk0e7nIuJbaJ9fJ6YJzUdK/oYy+9FZw5qRnIKFvitNBPXn8wEgD
eaaHsB/oaFTZiLSdHqlU5A23h1uyy06WogxiUfNw/V8OjLxr1Jg5w6Q+tklnZSson3
ImLND21tXvMjbvb+vr9syJP3Sks/bSC14SG5V4Tc++XcfVgD7dTFEThK7h9+NnjKjQ
oXuKJhfajL/RPniv4UDcQ/C34QrW61SnXAnYt8j8hK5pDFW6vYKeIuipn/DiyRxstl
5PjBLWc841dqvdFn9Qrx3SJbnoBXbhYuQm076yNhONKgq5SAyM

The State[i] = Message[i*8], for 0 <= i < 64 The coefficients are order from most significant to least (i.e, 64,63,62...) and were obtained using the Berlekamp-Massey algorithm. The coefficients and state were then plugged into an LFSR(coeff,state) to verify that the remaining 8th bits of the message could be predicted (i.e., that the initialization and setup were correct). So, I can step the LFSR to get more bits to figure out the base coefficients, but the steps are way too big. First step is 0, but second element is a jump forward a distance of the modulo inverse of 8 (mod (2**64)-1).