Tuesday, 11 September 2018

polynomials - Multiplicative Inverse in a $256$ Galois Field



I am working on finding the multiplicative reverse in $GF(2^8)$ using the Euclidean Algorithm but after reading multiple sources, I feel as though I am proceeding incorrectly. Using the irreducible polynomial $m(p)=x^8+x^4+x^3+x+1=0x11B$ I am trying to find the inverse of $x^6+x^4+x+1=0x53$



I know using long division (via http://www.wolframalpha.com/widgets/view.jsp?id=f396eaca9aaccbf858652bccc972324a) I get for the first step
$$(x^8+x^4+x^3+x+1)=(x^6+x^4+x+1)*(x^2-1)+(2x^4-x^2+2x+2)$$
but do I keep the negatives and even coefficients? I can't seem to get a reasonable answer and all the examples I have seen use simpler numbers. I know the answer to be $x^7+x^6+x^3+x=0xCA$ I just cannot seem to get there.


Answer



Here are the steps you should obtain.




\begin{align}
&x^8+x^4+x^3+x+1 = (x^6+x^4+x_1+1) (x^2 + 1) + x^2\\
&x^6+x^4+x+1 = x^2 (x^4 + x^2) + x + 1\\
&x^2 = (x+1) x + 1.
\end{align}


No comments:

Post a Comment

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...