We can represent $\mathbb{F}_{q^m}$ as $\mathbb{F}_q[\alpha]$ where $\alpha$ is root of an irreducible $m$-degree polynomial on $\mathbb{F}_q$. By sending $\sum_{i=0}^{m-1} c_i\alpha^i \mapsto (c_{m-1},\cdots,c_1,c_0)$ we have a map $\mathcal{J}:\mathbb{F}_{q^m}\mapsto(\mathbb{F}_q)^m$.
Let $\mathcal{P}_q$ be polynomial ring of polynomials having degree less than $q$ on $\mathbb{F}_q$. (we have $x^q=x$)
Let $\mathcal{P}_{q^m}$ be polynomial ring of polynomials having degree less than $q^m$ on $\mathbb{F}_q$. (we have $x^{q^m}=x$)
Then, we have a map $f:\mathcal{P}_{q^m} \rightarrow (\mathcal{P}_q)^m$. The map works as
- For any constant $c \in \mathbb{F}_{q^m}$, $f(c)=\mathcal{J}(c)$
- For any constant $c \in \mathbb{F}_{q^m}$ we have $\mathcal{J}(cx)=C\mathcal{J}(x)$ where $C$ is an $m\times m$ matrix
- $f$ sends $x^2\in \mathcal{P}_{q^m}$ to a quadratic $m$-variable $m$ polynomials.
Now, we can represent any polynomial in $\mathcal{P}_{q^m}$ as a polynomial in $(\mathcal{P}_q)^m$. I need the inverse of $f$. Especially, how can we calculate the $f^{-1}(Q)$ when $Q$ is a quadratic polynomial in $(\mathcal{P}_q)^m$.
We can prove that $f$ is invertible because it is one-to-one and the polynomial rings have the same order.
Let $m=50$ and $q=7$, then I feel that an algorithm calculating the map $f^{-1}$ has impractical time complexity. However, I hope that for a quadratic $Q$ there may be a practical way to find $f^{-1}(Q)$.
