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

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)?

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:

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$

• and, of course - polynomials must have 1 as gcd. Kinda implied here Apr 6, 2015 at 8:41
• Looks good to me. If you are planning on doing some coding here, you may want to consider using a few look-up-tables (unless working on tightly memory controlled device). See this thread for small toy examples using the discrete logarithm in performing the field arithmetic. In this question contains a link to a complete log table of $GF(256)$. Apr 6, 2015 at 18:05