# Isomorphism of finite dimensional polynomial algebras over finite fields

For a prime power $q$, consider polynomials $f_1,f_2 \in \mathbb{F}_q[x]$. Then, do we have an efficient way of checking 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},$$

and computing one such isomorphism if it exists?

I think an intermediate step will be to factorise $f_1$ and $f_2$ into products of irreducible polynomials over $\mathbb{F}_q$, which can be done efficiently using Cantor-Zassenhaus algorithm. Any hints on how to proceed?

As you mentioned, you can factor $f_1$ and $f_2$ in polynomial time. Consider the multiset $D_1$ of degrees of the factors of $f_1$, and the multiset $D_2$ of degrees of the factors of $f_2$. If $D_1 \ne D_2$, they are not isomorphic. If $D_1 = D_2$, they are isomorphic. That takes care of determining whether they are isomorphic.

Computing an isomorphism explicitly is harder. Let me focus first on the case where $f_1,f_2$ are squarefree, for ease of exposition. Note that if $f = g_1 \times \cdots \times g_m$, then we have a sort of Chinese remainder theorem:

$$\mathbb{F}_q[x]/\langle f\rangle \cong \mathbb{F}_q[x]/\langle g_1 \rangle \times \dots \times \mathbb{F}_q[x]/\langle g_m \rangle.$$

Consequently, by matching factors of same degree, you can reduce the problem to the case where $f_1,f_2$ are irreducible and $\deg f_1 = \deg f_2$ (in the squarefree case). Then both fields are isomorphic to $\mathbb{F}_{q^n}$, where $n= \deg f_1$.

Finding an isomorphism explicitly (if $f_1 \ne f_2$ and $\deg f_1 = \deg f_2$) looks related to the discrete log problem over $\mathbb{F}_{q^n}$. The discrete log problem is believed to be hard in general: the fastest algorithms currently known have a subexponential running time, and it is conjectured that there is no polynomial-time algorithm. In particular, it looks related to the Diffie-Hellman problem, and in most fields the Diffie-Hellman problem is probably as hard as the discrete log problem. I don't know of a reduction from discrete log or Diffie-Hellman to prove that finding an isomorphism is as hard as those problems, but I suspect there might be some relationship.

I do know that if you can compute the discrete log efficiently in $\mathbb{F}_{q^n}$, then you can exhibit an explicit isomorphism: pick a generator $g$ for the first field, and a generator $h$ for the second field; the isomorphism sends $g \mapsto g'$, and sends $g^k \mapsto h^k$, so given $x$, we compute the discrete log $k$ of $x$ to base $g$, then $x$ maps to $h^k$.

There's lots written about the discrete log problem in such finite fields. For the case where $q$ is small and $n$ is large, see for example https://crypto.stackexchange.com/q/228/351 and https://crypto.stackexchange.com/q/22332/351.

What about when $f_1,f_2$ are not squarefree? Then I think the problem is at least as hard. We can reduce to the case where $f_1 = p_1^e$ and $f_2 = p_2^e$, where $p_1,p_2$ are irreducible and $\deg p_1 = \deg p_2$. Then I think it might be possible to use Hensel lifting, though I haven't thought through the details. In particular, here is what happens with the discrete log. Consider the case where $e=2$. Let $g=a_1 p_1 + b_1$ be a generator of $\mathbb{F}_q[x]/\langle p_1^2 \rangle$. Note that

$$g^k = (a_1 p_1 + b_1)^k = k a_1 p_1 + b_1^k.$$

Therefore, to compute the discrete log of $x = a_2 p_1 + b_2$, it suffices to first find $k_0$ such that $b_1^{k_0} = b_2 \pmod{p_1}$ (which is the squarefree case of the discrete log considered above), then find $k$ such that $k \equiv k_0 \pmod{q^n-1}$ and $k \equiv a_2/a_1 \pmod{q^n}$, where $n = \deg p_1$. Such a $k$ can be found through the Chinese remainder theorem; you end up with $k = k_0 q^n - (a_2/a_1) (q^n-1)$. This shows how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1^2 \rangle$ if you know how to compute the discrete log in $\mathbb{F}_q[x]/\langle p_1 \rangle$. I think the same will apply to any $e>1$, not just $e=2$.

• I think there's a slight flaw in your reasoning. When you use Chinese remainder theorem, you'll get each $g_i$ to be a power of an irreducible and not necessarily irreducible. In that case, taking the quotient will not give us a field. – MathManiac Apr 26 '17 at 5:34
• @MathManiac, oh, good catch! You're quite right. I added some thoughts on that to the end of the question, but I haven't though it through carefully and I wouldn't vouch for it -- you should check the reasoning and see if you can work out the details more carefully than I did. – D.W. Apr 27 '17 at 5:58