Developed form of composition of polynomials in a finite field

43 Views Asked by At

Let $q=p^k$ be a prime power. Any polynomial $a(x)$ with coefficients in the finite field $\text{GF}(q)$ can be assimilated to a vector $a$ of $q-1$ elements $a_i\in\text{GF}(q)$, with (using the convention $x^0=1$ ) $$\begin{align} a(x)&=\sum_{0\le i\lt q-1}a_i\cdot x^i\\ &=a_{q-2}\,x^{q-2}+a_{q-3}\,x^{q-3}+\ldots+a_1\,x+a_0\\ &=(\ldots(a_{q-2}\,x+a_{q-3})\ldots\,x+a_1)\,x+a_0 \end{align}$$

The set $K[x]$ of such polynomials is a ring with addition $a+b$ and multiplication $a\cdot b$ of two polynomials such that $$\begin{align} (a+b)(x)&=\sum_{0\le i<q-1}(a_i+b_i)\,x^i\tag{1}\label{eq1}\\ (a\cdot b)(x)&=\sum_{0\le i<q-1}\biggl(\;\sum_{0\le j<q-1}a_j\cdot b_{(i-j\bmod(q-1))}\biggr)\,x^i\tag{2}\label{eq2} \end{align}$$

Further, $K[x]$ is a monoid under function composition $\circ$, with $a\circ b$ defined by $(a\circ b)(x)=a(b(x))$. The law $\circ$ is right-distributive with respect to polynomial addition and multiplication: $$\begin{align} \forall\,a,b,c\in K[x],\quad(a+b)\circ c&=(a\circ c)+(b\circ c)\\ (a\cdot b)\circ c&=(a\circ c)\cdot (b\circ c)\\ \end{align}$$

What's an expression for the coefficients of $a\circ b$ from these of $a$ and $b$ (similar to $\eqref{eq1}$ and $\eqref{eq2}$ for $+$ and $\cdot$ )? What's standard terminology for that operation on the vectors of coefficients?