Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Since all the finite field of $p^n$ elements are the splitting field of the separable polynomial $x^{p^n}-x$, all of them are isomphic. In particular if $f_1(x),f_2(x)$ are irreducible polynomials over $\mathbb{F}_p[x]$ of the same degree. Then: $$ \mathbb{F}_p[x]/(f_1(x)) \cong \mathbb{F}_p[x]/(f_2(x))$$ But I want to find an explicit isomorphism. I don't know if it's always possible. But the following could be useful.

Let's consider $f_2$ as a polynomial in $(\mathbb{F}_p[x]/(f_1(x)))[y]$. If $\gamma(x) $ is a root of $f_2(y)$ (a root on $\mathbb{F}_p[x]/(f_1(x))$). Then the following map is an isomorphism: $$\mathbb{F}_p[x]/(f_2(x)): \to \mathbb{F}_p[x]/(f_1(x)) $$ $$x\to \gamma(x)$$

My question if there are techniques to find that $\gamma(x)$.

For example if $f_1 = x^4+x^3+1 , f_2 = x^4+x+1 $ are over $\mathbb{F}_2$ then $\gamma(x)=x^3+x^2 $ it's a root.

If the solution of the general case it's not possible (or unsolved) or too difficult, I want to know at least this particular case :/ I want to compute it in the case $ f_1= x^2+2x+2 , f_2 = x^2+x+3 $ over $\mathbb{F}_7$

share|cite|improve this question
up vote 2 down vote accepted

In the field ${\mathbb F}_7[w]$ where $w^2 + 2 w + 2 = 0$, you want to find $\alpha$ such that $\alpha^2 + \alpha + 3 = 0$. It must be of the form $a + b w$ with $a, b \in {\mathbb F}_7$. Well, $(a+b w)^2 + a + b w + 3 = {a}^{2}+3+a-2\,{b}^{2}+ \left( b+2\,ab-2\,{b}^{2} \right) w$, so we want $ {a}^{2}+3+a-2\,{b}^{2} = 0$ and $ b+2\,ab-2\,{b}^{2} = 0$ mod 7. The solutions are $a=2,b=6$ and $a=4,b=1$.

share|cite|improve this answer
Are you sure that this result it's correct? Maybe I'm doing something wrong but, here's my understanding of the problem: I have to prove that for example $ \gamma(x)=2x+6 $ it's a root , of the polynomial $f_2$ over the field $ \mathbb{F}/(f_1(x)) $ Computing $f_2(\gamma ) = (2x+6)^2 + (2x+6) + 3 = 4x^2 + 36 + 24x + 2x+ 9 = 4x^2+ 5x + 3 $ But this is not cero $mod (f_1(x)) $ ( since it's clearly not a multiply of the polynomial $f_1$ ) . – Daniel Sep 27 '12 at 14:31
But it does not matter, but thanks to your idea I did the problem , Thanks! – Daniel Sep 27 '12 at 14:43
It's not $2x+6$, it's $2+6x$. $(2+6x)^2+(2+6x)+3 = 36 x^2 + 30 x + 9 \equiv 36 (x^2 + 2 x + 2) \mod 7$. – Robert Israel Sep 27 '12 at 17:43

At least for the case $n=2$, I believe the following works.

Let $q(x)$ and $r(x)$ be your irreducible polynomials. Without loss of generality, they're monic. We can complete the square and write them as $q(x) = (x+a)^2 + b$ and $r(x) = (x+c)^2 + d$.

Choose an automorphism of $\mathbb{F}_{p}$ called $\phi$ such that $\phi(b) = d$ (namely, multiplication of elements in $\mathbb{F}_p$ by $db^{-1}$). This automorphism induces an automorphism $\phi^\star$ of $\mathbb{F}_{p} [x]$ given by $$\phi^\star (a_n x^n + \cdots + a_0) = \phi(a_n) x^n + \cdots + \phi(a_0)$$

Let $k = c- \phi(a)$.

Then, the map $a + (q(x)) \mapsto \phi^\star (a) (x+k) + (r(x))$ is an isomorphism between $\mathbb{F}_{p}[x]/((q(x))$ and $\mathbb{F}_{p}[x]/((r(x))$.

share|cite|improve this answer

You can fctorize $f_2(y)\in\mathbb{F}_p[x]/(f_1(x))$ into linear facrors using factorization algorithms like Cantor–Zassenhaus algorithm or Berlekamp's algorithm . I think there are no easier way to do this in the general case.$ {} {} {} $

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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