# How to use Galois LFSR to find multiplicative inverses

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:

• 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$. – fgrieu Sep 26 '18 at 6:20
• "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$. – fgrieu Sep 26 '18 at 21:09