Find the elements of the extension field using primitive polynomial over $GF(4)$ Let $p(z) = z^2 + z + 2$ be a primitive polynomial. I want to construct the elements of the extensional field $GF(4^2)= GF(16).$ 
Since $p(z)$ is primitive polynomial , it should generate the elements of the extension field.
Let $\alpha$ be zero point then :


*

*$\alpha^2 + \alpha + 2 \rightarrow \alpha^2 = -\alpha-2 \rightarrow \alpha^2 = 3\alpha + 2$.


Using $\alpha$ : 


*

*$\alpha^1 = \alpha$

*$\alpha^2 = 3\alpha+2$ and according to the book, $\alpha^2 = \alpha+2$ but $-1 \mod 4 = 3$. 


Since the base is $4$ how can it be that the correct value of $\alpha^2 = \alpha + 2$?
I have mostly solved problems where the base is a prime number and the same procedure i have used here. 
 A: You seem confused about what $GF(4)$ is: it's not $\mathbb{Z}/(4)$ (which is not even a field).  You can represent $GF(4)$ as an extension of $GF(2)=\mathbb{Z}/(2)$ by an element $\beta$ such that $\beta^2=\beta+1$.  You can identify $GF(4)$ with the set $\{0,1,2,3\}$ by mapping $\beta$ to $2$ and $\beta+1$ to $3$, which appears to be what the book you refer to has in mind, but this does not mean you are working mod $4$ (the addition and multiplication operations are not ordinary mod $4$ addition and multiplication on $\{0,1,2,3\}$).
In particular, $1+1=0$ in $GF(4)$ and so $\alpha+2$ and $-\alpha-2$ are the same thing, and so you have $\alpha^2=\alpha+2$.
A: Here is an educated guess. You are confused by the difference between algebraic/arithmetic and computers representation of elements of $GF(4)$.
The field 
$$GF(4)=\{0,1,\beta,\beta+1\},$$
where the arithmetic comes from the rules $1+1=\beta+\beta=0$, $\beta^2=\beta+1$. The element $\beta$ (it could be denoted by something else if you wish) has no integer naturally associated with it.
However, in computer implementations we (including code written by yours truly worth a couple hundred CPU hours) we write the elements of $GF(4)$ as string of two bits:
$$0=00_2,\quad 1=01_2,\quad \beta=10_2,\quad \beta+1=11_2.$$
Do you see the idea? The element $b_0+b_1\beta$ is represented as the bitstring $b_1b_0$. Similarly we represent elements of $GF(2^m)$ as strings of $m$ bits. A big advantage of this is that addition in the field $GF(2^m)$ then becomes bitwise XOR of those bitstrings. Most (all?) computer hardwares have a superfast built-in function for performing bitwise XOR of two registers. So that's one of the basic arithmetic operations handed to us on a silver platter. Too good to pass up! The programmer only needs to worry about implementing the multiplication of $GF(2^m)$.
For smallish values of $m$ there are efficient ways of doing that (Caveat: there are other ways
of implementing e.g. $GF(4^2)$ even more efficiently for devices really short of memory). 

Anyway, having fixed an internal presentation of elements of $GF(2^m)$, programmers
  occasionally refer to them as integers represented by the same string of bits.

Because the integer $2$ is $10_2$ in binary, such a programmer may choose to refer to
$\beta$ as $2$ and $\beta+1$ as $11_2=3$. But they know that this is safe only among people in the know. If you do this in a general math forum, you are bound to confuse people. If you are a student still learning about this, you are bound to become confused by program documentation unless you first study this difference between algebraic notation and data representation internal to a computer.
So you may think of $GF(4)$ as the set $\{0,1,2,3\}$, but then you must  include rules like $1+1=0$, $2+2=0$, $3=2+1$ in the definition of your addition.
And, you also need to make rules like $2*2=3$, $2*3=1$ a part of your definition of multiplication. If you don't know this, you will be confused, and your questions will confuse others.
The above is all standard, but I claimed to have AN EDUCATED GUESS. Here it is.
If we present $\beta=2$ internally, then the quadratic
$$
p(x)=x^2+x+\beta "=" x^2+x+2
$$
is a primitive polynomial. It takes a bit of experience to see this at a glance.
But, see the last part of my linked answer (prepared with referrals like this in mind). You see that I explain there why $x^2+x+\beta$ is the minimal polynomial (over $GF(4)$) of some of the zeros of the well known primitive polynomial $x^4+x+1$ (over $GF(2)$).
So if $\alpha$ is a zero of $p(x)$ you can do the usual reduction business, and show that the elements $\alpha^i, i=0,1,\ldots,14$, are the non-zero elements of $GF(16)$,
and $\alpha^{15}=1$:
$$
\begin{aligned}
\alpha^2&=\alpha+\beta,\\
\alpha^3&=\alpha^2+\beta\alpha=(1+\beta)\alpha+\beta,\\
\alpha^4&=(1+\beta)\alpha^2+\beta\alpha=(1+\beta+\beta)\alpha+(1+\beta)\beta=\alpha+1,\\
\end{aligned}
$$
et cetera. All those powers of $\alpha$ can be written in the form $c_1\alpha+c_0$
where $c_0,c_1$ are elements of $GF(4)$. Feel free to continue that list.
If we revert to the $0,1,2,3$ notation of elements of $GF(4)$, the above calculation presents $\alpha^2$ as $\alpha+2$, $\alpha^3$ as $3\alpha+2$ and
$\alpha^4$ as $\alpha+1$. The last point proving that $\alpha$ is a zero of the primitive polynomial $x^4+x+1$ over $GF(2)$.
