how to find multiplicative inverse in a Galois field?

Question

How to find the multiplicative inverse of $$x^2+1 \pmod{x^4+x+1}$$

Answer 1

If the field has characteristic 5 things change. This is over the rationals.

$$ \left( x^{4} + x + 1 \right) $$

$$ \left( x^{2} + 1 \right) $$

$$ \left( x^{4} + x + 1 \right) = \left( x^{2} + 1 \right) \cdot \color{magenta}{ \left( x^{2} - 1 \right) } + \left( x + 2 \right) $$ $$ \left( x^{2} + 1 \right) = \left( x + 2 \right) \cdot \color{magenta}{ \left( x - 2 \right) } + \left( 5 \right) $$ $$ \left( x + 2 \right) = \left( 5 \right) \cdot \color{magenta}{ \left( \frac{ x + 2 }{ 5 } \right) } + \left( 0 \right) $$ $$ \frac{ 0}{1} $$ $$ \frac{ 1}{0} $$ $$ \color{magenta}{ \left( x^{2} - 1 \right) } \Longrightarrow \Longrightarrow \frac{ \left( x^{2} - 1 \right) }{ \left( 1 \right) } $$ $$ \color{magenta}{ \left( x - 2 \right) } \Longrightarrow \Longrightarrow \frac{ \left( x^{3} - 2 x^{2} - x + 3 \right) }{ \left( x - 2 \right) } $$ $$ \color{magenta}{ \left( \frac{ x + 2 }{ 5 } \right) } \Longrightarrow \Longrightarrow \frac{ \left( \frac{ x^{4} + x + 1 }{ 5 } \right) }{ \left( \frac{ x^{2} + 1 }{ 5 } \right) } $$ $$ \left( x^{4} + x + 1 \right) \left( \frac{ x - 2 }{ 5 } \right) - \left( x^{2} + 1 \right) \left( \frac{ x^{3} - 2 x^{2} - x + 3 }{ 5 } \right) = \left( -1 \right) $$

Answer 2

Easy by Inverse Reciprocity: $ $ first compute $\,\color{#0a0}{\large \frac{1}f} \,\bmod\, x^2\!+1,\,$ for $\, f = x^4\!+\!x\!+\!1,\,$ i.e.

$\!\!\bmod x^2\!+1\!:\ x\equiv i\,\Rightarrow\,\color{#0a0}{\dfrac{1}f}\equiv \dfrac{1}{i^4\!+\!i\!+\!1}\equiv \dfrac{1}{2+i}\equiv \color{#0a0}{\dfrac{2-i}5}\,$ by rationalizing denom

therefore $\ \color{#0a0}{\frac{1}5(2\!-\!x)}\, f = 1 + (x^2\!+\!1)\,\color{#c00}g,\ $ so

$\!\!\bmod f\!:\,\ \dfrac{1}{x^2\!+1}\equiv -\color{#c00}g\equiv \dfrac{1-\frac{1}5 (2\!-\!x) f}{x^2\!+1} \equiv {\large \frac{1}5}(x^3\!-2x^2\!-x+3)$

Answer 3

All the fancy methods are fine, but here’s a back-alley way of doing it, strongly dependent on which field $\Bbb F$ your coefficients come from:

In the case the constants are from the field with two elements, then the field in which $x^2+1$ sits has $16=2^4$ elements, and its multiplicative group is cyclic of order $15$. This means that any nonzero element of the big field, say $z$, satisfies the condition that $z^{15}=1$, and consequently $z^{-1}=z^{14}$, which is easily calculated as $[((z^2)\cdot z)^2\cdot z]^2$, which you can do with only five multiplications in your field.