Diffie-Hellman key exchange protocol with finite field GF(2^5) In a Diffie-Hellman key exchange protocol, the system parameters are given as
follows: finite field $GF(2^5)$ defined with irreducible polynomial $f(x) = x^5 + x^2 + 1$ and
primitive element $\alpha= x$ in the field.

Suppose that Alice selected random number $a = 5$ and Bob selected $b = 6$, show the steps
performed by Alice and Bob to obtain their shared key. What is the key?

For Alice:

$α^a = α^5 = x^5 = (x^2 + 1)$

For Bob:

$α^b = α^6 = x*x^5 = x(x^2 + 1) = x^3 + x$

Shared Key For Alice:

$α^{ab} = (x^2 + 1)^b = (x^2 + 1)^6\ldots$

Shared Key For Bob:

$α^{ab} = (x^3 + x)^a = (x^3 + x)^5\ldots$

The answer is $x^4 + x$ but I'm not sure how to simplify to this answer from both sides either Alice or Bob which should have the same shared Key
Three words Finite Field Arithmetic. The elements of the Finite Field (Galois field) can be represented by a polynomial, like in this case. We prefer it since it gave us good computing properties.

$GF(2^5)$ is a binary field extension with the base field 2, the binary field. To construct this field we need an irreducible binary polynomial [*] of degree  5[‡]. In your case it is $f(x)=x^5+x^2+1$. The field can be constructed by $GF(2)[x]/x^5+x^2+1$. An irreducable binary poynomial with degree 5 need not be unique, there is only 6 possibilities for constructing $GF(2^5)$ [#].


$f(x)=1+x^2+x^5$, 
$f(x)=1+x+x^2+x^3+x^5$,
$f(x)=1+x^3+x^5$,
$f(x)=1+x+x^3+x^4+x^5$,
$f(x)=1+x^2+x^3+x^4+x^5$, and 
$f(x)=1+x+x^2+x^4+x^5$


For the binary field extension and we prefer the ones with small degree monomials and with fewer monomials. So, $f(x)=1+x^2+x^5$  is a good choice.

The addition is polynomial addition with the coefficients are reduced to base field. Multiplication is a bit tricky, we need modulo reduction with the irreducible polynomial. In your case, whenever you see $x^5$ replace it with $x^2+1$. In this website, you can see the table for addition and multiplication. For small cases, generating the table and hardcoding it in a table can be helpful, however, be aware of the cache attacks.

One way is multiplying all at once then reduce
\begin{align}
(x^2 + 1)^6 &amp;= x^{12} + 6 x^{10} + 15 x^8 + 20 x^6 + 15 x^4 + 6 x^2 + 1 \\
            &amp;= x^{12} + x^8 + 15 x^4 + 1 \\
     \vdots &amp;= \vdots\\
\end{align}

This is not the preferred method since it can scale too much, especially for large finite fields. The better method is the multiply-and-reduce paradigm as below.

\begin{align}
(x^2 + 1)^6 &amp;= ((x^2 + 1)^2)^2 (x^2 + 1)^2  &amp;&amp;,\text{expand one level } \\
            &amp;= (x^4 + \color{red}{2} x^2 + 1)^2 (x^4 + \color{red}{2} x^2 + 1) &amp;&amp; , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &amp;= (x^4 + 1)^2 (x^4 + 1) &amp;&amp;,\text{work on left} \\
            &amp;= (x^8 + \color{red}{2}x + 1) (x^4 + 1)  &amp;&amp; , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &amp;= (x^8 + 1) (x^4 + 1)  &amp;&amp; , \text{use } x^5 = x^2+1\\ 
            &amp;= ((x^5)x^3 + 1) (x^4 + 1) \\
            &amp;= ((x^2+1)x^3 + 1) (x^4 + 1) \\
            &amp;= (x^5 + x^3 + 1 ) (x^4 + 1)&amp;&amp; , \text{use } x^5 = x^2+1\\
            &amp;= (x^2+ \color{red}{1} + x^3 + \color{red}{1} ) (x^4 + 1)&amp;&amp; , \color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &amp;= (x^3 + x^2 ) (x^4 + 1) &amp;&amp;, \text{multiply}\\
            &amp;= x^7 + x^6 + x^3 + x^2  &amp;&amp;,\text{use } x^5 = x^2+1\\
            &amp;= (x^2+1)x^2 + (x^2+1)x + x^3 + x^2 &amp;&amp;,\text{expand } \\
            &amp;= x^4 + \color{red}{2} x^3 + \color{red}{2} x^2 + x &amp;&amp;,\text{use }\color{red}{2=0} \text{ in } \mathbb{F}_2\\
            &amp;= x^4+ x &amp;&amp;  
\end{align} 

And, for the other equation, you can see their equality by; $$(x^3+x)^5=x^5(x^2+1)^5=(x^2+1)(x^2+1)^5=(x^2+1)^6$$

We, actually, use bit vector to process the binary polynomials:

$ (x^2+1)= [00101]$, we can represent with 5 bits since the finite field $GF(2^5)$.

Whenever we see, 1 out of size 5 we reduce it.


$ (x^5)= [1|00000] = [00101]$, the reduction is shift and x-or. We can say, replace the 1 with position 5 with $[0|00101]$ and x-or. Similarly, we can write formulas for 
$x^6 = (x^5)x = [01001]$ and 
$x^7 = (x^5)x^2 = [10100]$, and so on. In your case 6 should be enough if you multiply one by one.


\begin{align}
[00101]^6 &amp;= [00101]\cdot [00101]\cdot [00101]^4 \\
          &amp;= [10001]\cdot [00101]\cdot [00101]^3 \\ 
          &amp;= [10|10001]\cdot [00101]^3 \tag{use $x^6$}\\
          &amp;= [11000] \cdot [00101] \cdot [00101]^2\\  
          &amp;= [11|11000] \cdot [00101]^2\\ 
   \vdots &amp;= \vdots 
\end{align}



[*] A polynomial is said to be irreducible if it cannot be factored into nontrivial polynomials over the same field. (Wolfram defn.)

[#] The list is taken from Wolfram, too.

[‡] There is a sequence on the number of binary polynomials on the degree; OEIS A059912