Greatest common divisor of polynomial in Finite Field(256), AES

Question

Have assigment and will use it as example, found solution computationaly, want to understand idea.

It is about SubBytes procedure in AES, particulary about finding inverse of polynomial.

Suppose we have element $A=x^5+1$ in finite field $F=\mathbb{Z}_2[x]/x^8+x^4+x^3+x+1$ and it is required to compute $A^{-1}$, so that $AA^{-1}=1$

Computationally $A^{-1}=x^6 + x^5 + x^3 + x^2 + x$, $AA^{-1}=(x^5+1)(x^6 + x^5 + x^3 + x^2 + x)=x^{11} + x^{10} + x^8 + x^7 + x^5 + x^3 + x^2 + x$

Lets name $I=x^8+x^4+x^3+x+1$ for convenience, it is ideal of $F$. Then $AA^{-1}-I*x^3-I*x^2-I=1$, $AA^{-1}$ reduces to $1$ alright.

Well, how to get $A^{-1}=x^6 + x^5 + x^3 + x^2 + x$? This is where it gets messy for me.

It is my understanding, that $A^{-1}$ is found by eucleidean algorithm, in this case $(x^5+1)*A^{-1}+I*R=1$, where $R \in F$.

What I do.. try to do:

$(x^8+x^4+x^3+x+1)=(x^5+1)(x^3)+(x^4 + x + 1)$

$(x^5+1)=(x^4 + x + 1)(x)+(x^2 + x + 1)$ .. it is kinda mess, see work at Cloud Sage[Removed]

What I am doing wrong above, when I try to find F.xgcd(A)?

Answer 1

Took a lot of thought, had the right box but was looking in wrong corner.

Will answer myself, for own convenience will change letters a bit.

All coefficients are modulo 2, and it is required to find polynomials $P(x)$ and $Q(x)$ so that $A(x)P(x)+B(x)Q(x)=1$, where $A(x)=x^5+1$ and $B(x)=x^8+x^4+x^3+x^1+x^0$. Actually, we need only $P(x)=A^{-1}(x)$

Anyway:

$x^8+x^4+x^3+x+1=(x^5+1)(x^3)+(x^4+x+1)$ [1]
where
$(x^5+1)=(x^4+x+1)(x)+(x^2+x+1)$ [2]
where
$(x^4+x+1)=(x^2+x+1)(x^2+x)+(1)$ [3]
where, well
$(x^2+x+1)=(x^2+x+1)(1)+0$

Lets express $1$ from [3] by what we have in [1], ie
$1=(x^4+x+1)+((x^5+1)+(x^4+x+1)(x))(x^2+x)$
$1=(x^5+1)(x^2+x)+(x^4+x+1)(x^3+x^2+x)$
excellent, now lets substitute $x^4+x+1$ from [1]
$1=(x^5+1)(x^2+x)+((x^8+x^4+x^3+x+1)+(x^5+1)(x^3))(x^3+x^2)=$ $=A(x)(x^6+x^5+x^3+x^2+x)+B(x)(x^3+x^2+1)$

Where $A^{-1}=x^6+x^5+x^3+x^2+x$, which was looked for. $\Box$

Answer 2

If I understand your problem:

Suppose we have element $A=x^5+1$ in finite field $F=\mathbb{Z}_2[x]/(x^8+x^4+x^3+x+1)$ and it is required to compute $A^{-1}$, so that $AA^{-1}=1$

This means that we are looking for an element $B$ such that : $AB=BA=1$ in $F$, this means in terms of polynomials that there exists $Q$ such that: $$A(x)B(x)=1+Q(x)\cdot (x^8+x^4+x^3+x+1) $$ And if this identity is satisfied we say that $B$ is the inverse of $A$ and denoted by $B=A^{-1}$ (To see things clearly you can make an analogy with $\mathbb{Z_p}$ and try to find the inverse of an element);

Now, how can we compute the inverse of an element? we use generally the Extended Euclidean algorithm and here are some references explaining exactly the same problem:

• Finding the inverse of an element in finite field
• How to use the Extended Euclidean Algorithm manually?
• Algorithm for computing the inverse of a polynomial