My question is how can a Galois Linear Feedback Shift Register be used to discover multiplicative inverses of polynomials?

This is a homework assignment. Here is a list of things I did before asking here:

  • Learned about finite fields
  • Learned how to do modular arithmetic with polynomials
  • Learned about multiplicative inverses in Galois extension fields
  • Simulated several different LFSRs on paper
  • Plowed through all of my course material

I've got nothing.

  • 2
    $\begingroup$ Hint: if $S_0$ is the initial state of a Galois LFSR with polynomial $P$, then after $i$ steps the state is $S_i=S_0\,x^i\bmod P$. $\endgroup$ – fgrieu Sep 26 '18 at 6:20
  • $\begingroup$ Is there supposed to be some really simple and obvious way to find the multiplicative inverse? The way I interpret your answer is that I'm supposed to simulate the LFSR until the state equals 1, and then I need to calculate what x is, after which I need to calculate x^i mod P. This seems much more difficult than finding the inverse without the LFSR. $\endgroup$ – Atte Juvonen Sep 26 '18 at 14:47
  • $\begingroup$ "Calculating what $x$ is" has no meaning; $x$ is purely notational. You guessed roughly half of the simple method I suggest. Hint2: the LFSR itself can then be used to compute $x^i\bmod P$ knowing $i$. $\endgroup$ – fgrieu Sep 26 '18 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.