Let $n \in\mathbb N^*$.
What are all the surjective functions $f: \mathbb N \rightarrow \{0,...,n-1\}=E $ such that there exist functions $g,h$ from $E^2$ to $E$ with:
$\forall (m,k) \in\mathbb N^2,f(m+k)=g(f(m),f(k)), and f(m\times k)=h(f(m),f(k))$ ?
Even if we have only $f(m+k)=g(f(m),f(k))$, these functions may be classified as follows.
It is more convenient to consider not the function $f$, but the corresponding equivalence relation: $a\sim b$ iff $f(a)=f(b)$. Then we are given that this equivalence relation is sum-invariant: if $m_1\sim m_2$, $k_1\sim k_2$ then $m_1+k_1\sim m_2+k_2$. And viceversa, any such equivalence relation with finitely many classes naturally correspond to several (essentially unique) choices of $f,g$. So, further I classify only sum-invariant equivalence relations with finitely many classes.
Choose a positive integer $d$ and $N\in \mathbb{N}$. Consider the following relation: all numbers less than $N$ form singleton classes; and numbers which are not less $N$ form another $d$ classes which are residue classes modulo $d$. In other words, $a\sim b$ if and only if either $a=b<N$ or $a,b\geqslant N$ and $a\equiv b \pmod d$.
It is straightforward to check that such equivalence relation is sum-invariant. I claim that every sum-invariant equivalence relation $\sim$ on $\mathbb{N}$ with finitely many classes is of such form.
We call an integer $T>0$ an eventual period of $\sim$, if $n\sim n+T$ for all large enough $T$. If $a\sim b$ and $a>b$, then $b-a$ is an eventual period: $n+b-a=(n-a)+b\sim (n-a)+a=a$ whenever $n>a$. So, since the numberof classes is finite, eventual periods exist.
Next, if $T_2>T_1$ are eventual periods, then so is $T_2-T_1$: indeed, $n+T_2-T_1\sim n+T_2\sim n$ for large enough $n$. Thus, if $d$ is the minimal eventual period, then all other eventual periods are multiples of $d$. Then, if $x\sim y$, then, since $x-y$ is an eventual period, we conclude that $x\equiv y \pmod d$. Choose minimal $N_0\in \mathbb{N}$ such that whenever $a,b\geqslant N_0$ and $a\equiv b \pmod d$, we have $a\sim b$. By minimality of $N_0$, $N_0-1$ and $N_0-1+d$ are not equivalent. What remains to prove is that all natural numbers less than $N_0$ form singleton equivalence classes. Assume the contrary, the there exists $x<N_0$ and $k>0$ such that $x\sim x+k$. We have $d|k$. Next, $$N_0-1=x+(N_0-1-x)\sim (x+k)+(N_0-1-x)=N_0-1+k\sim N_0-1+d,$$ a contradiction.
