Arithmetic in the finite field $\mathbb{F}_{2^4}$

Question

In this document: "The Elliptic Curve Digital Signature Algorithm (ECDSA)" - Don Johnson, Alfred Menezes, Scott Vanstone; in section 4.2 example 7 there is some finite field arithmetic:

Given $\alpha \in \mathbb{F}_{2^4}$ the following is claimed: $$ \begin{align*} & \quad \left( \frac{\alpha^8 + \alpha^{13}}{\alpha^6+\alpha^3} \right)^2 + \frac{\alpha^8 + \alpha^{13}}{\alpha^6+\alpha^3} + \alpha^6 + \alpha^3 + \alpha^4 \\ &=\left( \frac{\alpha^3}{\alpha^2} \right)^2 + \frac{\alpha^3}{\alpha^2} + \alpha^6 + \alpha^3 + \alpha^4 \\ &= 1 \end{align*} $$

I don't understand the simplification that is happening line-by-line. I tried using some concrete examples, like $\alpha=x$ or $\alpha=x+1$ and then sure enough the simplification works out (I used https://wims.math.cnrs.fr/wims/wims.cgi to double check my working).

The irreducible poly chosen in the text is $f(x) = x^4 + x + 1$ (not sure if it's relevant in the general case for $\alpha$).

Answer 1

A bit earlier, in section 3.2.1, example 2, they explicitly say $\alpha=x$.

Answer 2

By assumption we have $2=0$ and $\alpha^4=\alpha+1$, so that $\alpha^6=\alpha^3+\alpha^2$. Now the computation is just $$ \left( \frac{\alpha^3}{\alpha^2} \right)^2 + \frac{\alpha^3}{\alpha^2} + \alpha^6 + \alpha^3 + \alpha^4 =2(\alpha+\alpha^2+\alpha^3)+1=1. $$

Answer 3

It is very relevant which polynomial we choose to extend $\Bbb F_2$ to $\Bbb F_{2^4}$. It tells us that $\alpha$ is a root of the polynomial, and therefore that $\alpha^4+\alpha+1=0$, alternately that $\alpha^4+\alpha=1$ or $\alpha^4=\alpha+1$ (remember we are in characteristic $2$). Using this we get $$ \alpha^{13}=\alpha\cdot(\alpha^4)^3=\alpha\cdot(\alpha+1)^3=\alpha^4+\alpha^3+\alpha^2+\alpha\\ =(\alpha+1)+\alpha^3+\alpha^2+\alpha=\alpha^3+\alpha^2+1 $$ Similarly we get $$ \alpha^8=(\alpha^4)^2=(\alpha+1)^2=\alpha^2+1 $$ Adding these two together yields $\alpha^8+\alpha^{13}=\alpha^3$. A very similar but simpler calculation yields $\alpha^6+\alpha^3=\alpha^2$.

Obviously we have $\frac{\alpha^3}{\alpha^2}=\alpha$, and the rest is simply collecting like terms and cancelling using $2=0$.

Answer 4

Years ago I prepared this Q&A pair with exactly referrals like this in mind. The discrete logarithm table in that answer applies here, because I also used $f(x)=x^4+x+1$ as the primitive polynomial. The only difference is that I denoted by $\gamma$ what your source calls $\alpha$ (mostly because $\alpha$ had a different meaning in my post, normally I would also denote it $\alpha$ :-).

I will show how to use that table.

• We have $\alpha^8=\alpha^2+1$ and $\alpha^{13}=\alpha^3+\alpha^2+1$, so $\alpha^8+\alpha^{13}=\alpha^3$.
• We have $\alpha^6=\alpha^3+\alpha^2$, so $\alpha^6+\alpha^3=\alpha^2$.
• Therefore $(\alpha^8+\alpha^{13})/(\alpha^3+\alpha^6)=\alpha^3/\alpha^2=\alpha$.
• $\alpha^4=\alpha+1$, so that formula evaluates to $$\alpha^2+\alpha+(\alpha^3+\alpha^2)+\alpha^3+(\alpha+1)=1.$$