Extended Euclidean Algorithm in $GF(2^8)$? I'm trying to understand how the S-boxes are produced in the AES algorithm. I know it starts by calculating the multiplicative inverse of each polynomial entry in $GF(2^8)$ using the extended euclidean algorithm. However I am having some trouble understanding how to perform the euclidean algorithm with polynomials in a field. Could someone please explain how to do this with a step by step example?
 A: Using Rijndael's finite field, the reducing polynomial is $x^8+x^4+x^3+x+1$.
Suppose we want to compute the inverse of $x^5+1$ in this field. We want to solve the equation
$$
a(x^5+1)+b(x^8+x^4+x^3+x+1)=1
$$
I like to use the Euclid-Wallis Algorithm. Since we are dealing with polynomials, I will write things rotated by $90^\circ$.
$$
\begin{array}{c|c}
x^8+x^4+x^3+x+1&0&1&\\\hline
x^5+1&1&0\\\hline
x^4+x+1&x^3&1&x^3\\\hline
x^2+x+1&x^4+1&x&x\\\hline
\color{#C00000}{1}&\color{#C00000}{x^6+x^5+x^3+x^2+x}&\color{#C00000}{x^3+x^2+1}&x^2+x\\\hline
0&x^8+x^4+x^3+x+1&x^5+1&x^2+x+1
\end{array}
$$
The fifth row tells us that in $\mathbb{Z}_2[x]$
$$
(x^5+1)(\color{#C00000}{x^6+x^5+x^3+x^2+x})+(x^8+x^4+x^3+x+1)(\color{#C00000}{x^3+x^2+1})=\color{#C00000}{1}
$$
Thus, $x^6+x^5+x^3+x^2+x$ is the inverse of $x^5+1$ in $\left.\mathbb{Z}_2[x]\middle/(x^8+x^4+x^3+x+1)\mathbb{Z}_2[x]\right.$.
A: Here is the java code for EEAP for polynomials .
There are two Polynomials f(x) and G(x) over the finite field M(x) and primeNumber.
package polynomial;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
class PolyFunction {
    private int degree;
    private int coeff[];
PolyFunction(int deg, int coef) {
    this.coeff = new int [deg+1];
    this.coeff[deg] = coef;
    this.degree  = deg;
}
int getDegree() {
    int d = 0;
    for (int i = 0; i < coeff.length; i++)
        if (coeff[i] != 0) d = i;
    return d;
}
void checkMode(int primeNumber) {
    for (int i = 0; i <= getDegree(); i++) {
        coeff[i] %= primeNumber;
        if (coeff[i] < 0) 
            coeff[i] += primeNumber;
    }

}

PolyFunction addition(PolyFunction gx,int primeNumber) {
    PolyFunction fx = this;     
    PolyFunction fPlusG = new PolyFunction(Math.max(fx.degree, gx.degree),0);
    for (int i = 0; i <= fx.degree; i++) {
        fPlusG.coeff[i] += fx.coeff[i];
    }
    for (int i = 0; i <= gx.degree; i++) {
        fPlusG.coeff[i] += gx.coeff[i];
    }
    fPlusG.checkMode(primeNumber);
    return fPlusG;
}

PolyFunction minus(PolyFunction gx, int primeNumber) {
    PolyFunction fx = this;
    PolyFunction fMinusg = new PolyFunction(Math.max(fx.degree, gx.degree), 0);
    for (int i = 0; i <= fx.degree; i++) {
        fMinusg.coeff[i] += fx.coeff[i];
    }
    for (int i = 0; i <= gx.degree; i++) {
        fMinusg.coeff[i] -= gx.coeff[i];
    }
    fMinusg.checkMode(primeNumber);
    //fMinusg.degree = fMinusg.getDegree();
    return fMinusg;
}

PolyFunction multiple(PolyFunction gx) {
    PolyFunction fx = this;
    PolyFunction fMulg = new PolyFunction(fx.degree + gx.degree, 0);
    for (int i = 0; i <= fx.degree; i++)
        for (int j = 0; j <= gx.degree; j++)
            fMulg.coeff[i+j] += (fx.coeff[i] * gx.coeff[j]);

    return fMulg;
}

PolyFunction[] PLDA(PolyFunction gx, int primeNumber) {
    PolyFunction fx  = this;

    fx.checkMode(primeNumber);
    gx.checkMode(primeNumber);

    PolyFunction []qr = new PolyFunction[2]; 
    qr[1] = fx;
    qr[0] = new PolyFunction(0,0);

    int degofQ = fx.getDegree() - gx.getDegree() ;

    if (degofQ == 0 && gx.getDegree() == 0) {
        //System.out.println("deg is zero");
        int temp [] = EEA(primeNumber, gx.coeff[0]);
        int divResult = (qr[1].coeff[qr[1].getDegree()] * temp[1]);

        divResult %= primeNumber;
        if ( divResult < 0) 
            divResult += primeNumber;
        qr[0] = new PolyFunction((qr[1].getDegree()-gx.getDegree()), divResult);
        qr[1] = new PolyFunction(0, 0);
        return qr;
    }

    if (degofQ < 0) {

        qr[1] = gx;
        qr[0] = fx;
        return qr;
    }

    while((qr[1].getDegree() >= gx.getDegree()) && (qr[1].getDegree()!=0 && qr[1].coeff[0]!=0)) {

        int [] temp = EEA(primeNumber,gx.coeff[gx.getDegree()]);

        int divResult = (qr[1].coeff[qr[1].getDegree()] * temp[1]);

        divResult %= primeNumber;
        if ( divResult < 0) 
            divResult += primeNumber;
        PolyFunction tx = new PolyFunction((qr[1].getDegree()-gx.getDegree()), divResult);

        qr[0] = qr[0].addition(tx,primeNumber);

        PolyFunction txgx = tx.multiple(gx);

        qr[1] = qr[1].minus(txgx,primeNumber);

        qr[0].checkMode(primeNumber);
        qr[1].checkMode(primeNumber);

    }
    return qr;
}

PolyFunction[] EEAP(PolyFunction gx,int primeNumber) {
    PolyFunction fx = this;
    PolyFunction []qr = new PolyFunction[2];

    if ((gx.getDegree() == 0) && gx.coeff[0] == 0) {            
        int [] temp = EEA(primeNumber,fx.coeff[fx.getDegree()]);

        int divResult = (1 * temp[1]);
        divResult %= primeNumber;
        if ( divResult < 0) 
            divResult += primeNumber;

        qr[0] = new PolyFunction(0, divResult);
        qr[1] = new PolyFunction(0, 0);
        return qr;
    }
    else {
            PolyFunction []R = new PolyFunction[2];
            qr = fx.PLDA(gx,primeNumber);
            PolyFunction q = qr[0];
            PolyFunction r = qr[1];
            R = gx.EEAP(r,primeNumber);

            PolyFunction ux = R[1];
            ux.checkMode(primeNumber);

            PolyFunction vx = R[0].minus(q.multiple(R[1]), primeNumber);
            vx.checkMode(primeNumber);
            return new PolyFunction[]{ux,vx};
    }
}

public int[] EEA(int a, int b){        
    if(b == 0){             
        return new int[]{1,0};                        
    } else {
        int q = a/b; 
        int r = a%b;
        int[] R = EEA(b,r);   
        return new int[]{R[1], R[0]-q*R[1]};
    }
}
public String toString() {
    if (degree ==  0) return "" + coeff[0];
    if (degree ==  1) return coeff[1] + "x + " + coeff[0];

    String ret = coeff[getDegree()] + "x^" + getDegree();

    for (int i = getDegree()-1; i >= 0; i--) {
        if      (coeff[i] == 0) continue;
        else if (coeff[i]  > 0) ret = ret + " + " + ( coeff[i]);
        else if (coeff[i]  < 0) ret = ret + " - " + (-coeff[i]);
        if      (i == 1) ret = ret + "x";
        else if (i >  1) ret = ret + "x^" + i;
    }
    return ret;
}

}
public class GF2 {
    private PolyFunction fx;
    private PolyFunction gx;
    private PolyFunction mx;
    private int primeNumber;
GF2(String file) {
    fx = gx = mx = null;
    if (readInput(file) == -1) 
        return;
    System.out.println("PrimeNumber is " + primeNumber);
    System.out.println("mx is " + mx);
    System.out.println("fx is " + fx);
    System.out.println("gx is " + gx);
}
private int readInput(String file) {
    int mxDeg = 0, fxDeg = 0, gxDeg = 0;
    try {
        int counter = 1;
        FileReader fileReader = new FileReader(file);
        BufferedReader bufferedReader = new BufferedReader(fileReader);
        String data = null;

        while(( data= bufferedReader.readLine()) != null) {
            switch(counter) {
            case 1:
                primeNumber = Integer.parseInt(data);
                break;
            case 2:
                mxDeg = Integer.parseInt(data);
                break;
            case 3:
                String [] mxToken = data.split("\\s+");
                PolyFunction []p = new PolyFunction[mxToken.length+1];
                for(int i=0; i < mxToken.length; i++) {
                     p[i] = new PolyFunction(mxDeg-i, Integer.parseInt(mxToken[i]));
                }
                mx = p[0];
                for(int i=1; i < mxToken.length; i++)
                    mx = mx.addition(p[i],primeNumber);
                break;
            case 4:
                fxDeg = Integer.parseInt(data);;
                break;
            case 5:
                String [] fxToken = data.split("\\s+");
                PolyFunction []pf = new PolyFunction[fxToken.length+1];
                for(int i=0; i < fxToken.length; i++) {
                     pf[i] = new PolyFunction(fxDeg-i, Integer.parseInt(fxToken[i]));
                }
                fx = pf[0];
                for(int i=1; i < fxToken.length; i++) 
                    fx = fx.addition(pf[i], primeNumber);
                break;
            case 6:
                gxDeg = Integer.parseInt(data);
            case 7:
                String [] gxToken = data.split("\\s+");
                PolyFunction []pg = new PolyFunction[gxToken.length+1];
                for(int i=0; i < gxToken.length; i++) {
                     pg[i] = new PolyFunction(gxDeg-i, Integer.parseInt(gxToken[i]));
                }
                gx = pg[0];
                for(int i=1; i < gxToken.length; i++) 
                    gx = gx.addition(pg[i],primeNumber);
                break;
            }
            counter++;
        }   
        bufferedReader.close();
    } catch (FileNotFoundException e) {
        System.out.println("Input file is not able to open");
        return -1;
    } catch (IOException e) {
        e.printStackTrace();
        return -1;
    }
    return 0;
}
void dmas() {
    System.out.println("Addition is : " + fx.addition(gx, primeNumber));
    System.out.println("Subtraction is : " + fx.minus(gx, primeNumber));
    PolyFunction fMulg = fx.multiple(gx);
    if (fMulg.getDegree() >= mx.getDegree()) {
        fMulg = fMulg.PLDA(mx,primeNumber)[1];
        fMulg.checkMode(primeNumber);
    }
    System.out.println("Multiplication is : " + fMulg.toString());

    PolyFunction fDivg = mx.EEAP(gx,primeNumber)[1];
    fDivg = fx.multiple(fDivg);
    if (fDivg.getDegree() >= mx.getDegree()) {
        fDivg = fDivg.PLDA(mx,primeNumber)[1];
        fDivg.checkMode(primeNumber);
    }

    System.out.println("Division is : " + fDivg);

}
public static void main(String[] args) {
    String file = "src\\polynomial\\myinput.txt";
    GF2 obj = new GF2(file);
    obj.dmas();
}

}
//
In “input.txt”: 
1.  First line is the prime number p.
2.  Second line is the degree n of the irreducible polynomial m(x) over Zp.
3.  Third line is the coefficients of m(x), from the leading coefficient to the constant, separated by one blank space.
4.  Fourth line is the degree of f(x) over Zp.
5.  Fifth line is the coefficients of f(x), from the leading coefficient to the constant, separated by one blank space.
6.  Sixth line is the degree of g(x) over Zp.
7.  Seventh line is the coefficients of g(x), from the leading coefficient to the constant, separated by one blank space.
//
Suppose we have data in input is
1> 7
2> 3
3> 1 0 0 3
4> 2
5> 2 0 1
6> 1
7> 3 2
output is
1> PrimeNumber is 7
2> mx is 1x^3 + 3
3> fx is 2x^2 + 1
4> gx is 3x + 2
5> Addition is : 2x^2 + 3x + 3
6> Subtraction is : 2x^2 + 4x + 6
7> Multiplication is : 4x^2 + 3x + 5
8> Division is : 6x^2 + 6x + 3
