How can I compute $A(x)+B(x) \mod P(x)$ in $\operatorname{GF}(2^4)$ using the irreducible polynomial $P(x)=x^4+x+1$. What is the influence of the choice of the reduction polynomial on the computation?
$A(x)=x^2+1, B(x)=x^3+x^2+1$
$A(x)=x^2+1, B(x)=x+1$
On
When the operands are given in their standard form (as polynomials of degree less than $n$), addition in $\mathrm{GF}(p^n)$ does not depend on which irreducible polynomial you use.
Just add each pair of matching coefficients and reduce it modulo $p$:
$$\begin{align} &(x^2+1)+(x^3+x^2+1) \\=&(0x^3+1x^2+0x+1)+(1x^3+1x^2+0x+1) \\=& (0+1)x^3+(1+1)x^2+(0+0)x+(1+1) \\=& 1x^3+0x^2+0x+0 \\=& x^3 \end{align}$$ because $1+1\equiv 0 \pmod 2$.
Addition on $GF(2^4)$ is made by adding the polynomials and reducing the coefficients mod 2. Multiplication is done by first multiplying the polynomials in the classical way (and reducing the coefficients mod 2) then reducing the degree of the polynomial to a degree at most 3 by using $x^4=-x-1=x+1$.
So in your first example, $$ (x^2+1)+(x^3+x^2+1)=x^3 + 2x^2+2=x^3 $$ and \begin{align} (x^2+1)(x^3+x^2+1)&=x^5+x^4+x^2+x^3+x^2+1\\&=(x+1)x^4+x^3+1\\&=x^3+(x+1)(x+1)+1\\&=x^3+x^2+2x+2\\&=x^3+x^2 \end{align}