Isomorphism between quotient rings over finite fields For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, how do we check whether there exists an algebra isomorphism between:
$$\frac{\mathbb{F}_q[x]}{\langle f_1 \rangle} \text{and} \frac{\mathbb{F}_q[x]}{\langle f_2 \rangle}?$$ 
This probably has something to do with factorising $f_1$ and $f_2$, and using Chinese Remainder Theorem, but I don't see how exactly.
 A: Here is a proof for the following proposition:

If $q$ is any prime power and $f,g \in \mathbb F_q[x]$ irreducible of
  the same degree $d$, then there is an isomorphism of $\mathbb
F_q$-algebras $\mathbb F_q[x]/(f^n) \cong \mathbb F_q[x]/(g^n)$.

This proposition answers the question, using the Chinese remainder theorem.
First let me proof the following easy lemma:

If $l$ is a prime power and $A \supset \mathbb F_l$ an algebra with $l^2$ elements and an element $0 \neq a \in A$ with $a^2=0$, then $A$ is isomorphic to $\mathbb F_l[\varepsilon]/(\varepsilon^2)$.

Proof. We clearly get a morphism $\mathbb F_l[\varepsilon]/(\varepsilon^2) \to A$ by sending $\varepsilon \mapsto a$, which is injective because $\varepsilon$ is not contained in the kernel. Comparing the number of elements shows that it is an isomorphism.
Now we can proof the proposition above:
We know the statement is true for $n=1$, i.e. we have an isomorphism $$\mathbb F_q[x]/(f) \to \mathbb F_q[x]/(g).$$
Choosing such an isomorphism is nothing else but choosing a polynomial $h \in \mathbb F_q[x]$ with $f(h(x)) = 0 \pmod{g(x)}$.
If $f(h(x)) \neq 0 \pmod{g(x)^2}$ we are done, because in this case we have that $f(h(x))^n \neq 0 \pmod{g(x)^n}$ and $f(h(x))^{n-1} \neq 0 \pmod{g(x)^n}$, thus we get a well-defined injective morphism $$\mathbb F_q[x]/(f^n) \to \mathbb F_q[x]/(g^n)$$ by sending $x \mapsto h(x)$, which is again an isomorphism by comparing number of elements.
If $f(h(x)) = 0 \pmod{g(x)^2}$, we get a well-defined morphism $\mathbb F_q[x]/(f) \to \mathbb F_q[x]/(g^2)$, i.e. $\mathbb F_q[x]/(g^2)$ is an algebra over $\mathbb F_{q^d}$ which clearly satisfies the assumptions of the lemma above, i.e. it is isomorphic to $\mathbb F_{q^d}[\varepsilon]/(\varepsilon^2)$.
So - for $n=2$ - we have shown the following:
If $f(h(x)) \neq 0 \pmod{g(x)^2}$, then we have the desired isomorphism.
If $f(h(x)) = 0 \pmod{g(x)^2}$, then $\mathbb F_q[x]/(g^2)$ is isomorphic to $\mathbb F_{q^d}[\varepsilon]/(\varepsilon^2)$
Of course we can switch roles of $f$ and $g$ and get an $h'$ with:
If $g(h'(x)) \neq 0 \pmod{f(x)^2}$, then we have the desired isomorphism.
If $g(h'(x)) = 0 \pmod{f(x)^2}$, then $\mathbb F_q[x]/(f^2)$ is isomorphic to $\mathbb F_{q^d}[\varepsilon]/(\varepsilon^2)$
Summarizing, we have shown the result for $n=2$, i.e. we have an isomorphism $$\mathbb F_q[x]/(f^2) \to \mathbb F_q[x]/(g^2).$$
Now we repeat our argument: Choosing such an isomorphism is nothing else but choosing a polynomial $h \in \mathbb F_q[x]$ with
(i) $f(h(x))^2 = 0 \pmod{g(x)^2}$, but
(ii)$f(h(x)) \neq 0 \pmod{g(x)^2}$.
The first property yields (iii) $f(h(x)) = 0 \pmod{g(x)}$. Like already explained (ii),(iii) yield an isomorphism
$$\mathbb F_q[x]/(f^n) \to \mathbb F_q[x]/(g^n).$$

Edit:
For the original question, I claimed a condition in the comments, which is clearly sufficient. Here is an easy argument that it is necessary:
W.l.o.g let $n_1$ be the largest among all multiplicities $n_i,m_j$. Then $\mathbb F_q[x]/(f)$ has an nilpotent element of nilpotence order $n_1$, namely $f_1$. So the ring has $\mathbb F_q[x]/(g)$ has also such an element, say $\phi(f_1)$. This shows some $m_j$ must be at least $n_1$. By the maximality of $n_1$, we get that some $m_j$ is equal to $n_1$, w.l.o.g it is $m_1$. After dividing out $f_1$ in $\mathbb F_q[x]/(f)$ and its image in $\mathbb F_q[x]/(g)$, we get an isomorphism $\mathbb F_q[x]/(f_1) \cong \mathbb F_q[x]/(\phi(f_1))$, thus we deduce that $\deg f_1 = \deg \phi(f_1)$ and $\phi(f_1)$ is irreducible. This yields $\varphi(f_1)=g_1$. So we have shown that the multiplicity and the degree of one of the irreducible factors coincides. The rest is an induction argument.
