1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MathManiac Apr 26 '17 at 5:34
  • $\begingroup$ @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. $\endgroup$ – D.W. Apr 27 '17 at 5:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.