# An efficient isomorphism between finite fields

Let $p$ be a prime number. Let $f$ and $g$ be irreducible polynomials over $\mathbb{F}_p$, both of degree $n$. We know that factor-rings $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ are isomorphic (both of them is isomorphic to $\mathbb{F}_{p^n}$).

My question is: Is it possible to make this isomorphism efficient? I.e. can we find a matrix that makes an isomorphism between $\mathbb{F}_p[x]/(f)$ and $\mathbb{F}_p[x]/(g)$ for poly(n) operations in $\mathbb{F}_p$?

• It is equivalent to finding a root of $g$ in $\mathbb{F}[p]/(f)$. There are many algorithms to factorize polynomials, in particular for finding their roots. – Fedor Petrov Jul 3 '16 at 15:53
• @FedorPetrov: although there are many algorithms to factorize polynomials over a finite field, there is no known deterministic polynomial time algorithm for doing this. However, there is a known deterministic polynomial time algorithm for finding a root of a polynomial over a finite field. Anyway I just wanted to mention that these problems are of different complexities, according to current understanding. – Michael Zieve Jul 4 '16 at 2:31
• @MichaelZieve Could you give a reference for a deterministic polynomial time algorithm for finding a root of a polynomial over a finite field – Alexey Milovanov Jul 6 '16 at 11:49
• @Alexey I should have added several conditions in what I said, since I was just trying to describe the case of root-finding which is equivalent to the problem Lenstra solved (namely finding isomorphisms between finite fields). There is a deterministic polynomial time algorithm which, for any two irreducible degree-$n$ polynomials $f_1,f_2\in\mathbf{F}_p[x]$, finds a root of $f_1(x)$ in the field $\mathbf{F}_p[x]/(f_2(x))$. The reference is Lenstra's paper on finding isomorphisms between finite fields. – Michael Zieve Jul 6 '16 at 14:17
• @MichaelZieve thank you, however for the general situation we do not know such an algorithm, don't we? – Alexey Milovanov Jul 6 '16 at 14:21