12
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – Fedor Petrov Jul 3 '16 at 15:53
  • 3
    $\begingroup$ @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. $\endgroup$ – Michael Zieve Jul 4 '16 at 2:31
  • $\begingroup$ @MichaelZieve Could you give a reference for a deterministic polynomial time algorithm for finding a root of a polynomial over a finite field $\endgroup$ – Alexey Milovanov Jul 6 '16 at 11:49
  • $\begingroup$ @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. $\endgroup$ – Michael Zieve Jul 6 '16 at 14:17
  • $\begingroup$ @MichaelZieve thank you, however for the general situation we do not know such an algorithm, don't we? $\endgroup$ – Alexey Milovanov Jul 6 '16 at 14:21
13
$\begingroup$

Google provides an answer to this question. The first deterministic polynomial time algorithm for this is due to H. W. Lenstra, Jr., in his paper "Finding isomorphisms between finite fields" (Mathematics of Computation, v. 56 (1991), 329-347). Another algorithm appears in the paper by B. Allombert, "Explicit computation of isomorphisms between finite fields" (Finite Fields and their Applications, v. 8 (2002), 332-342). However, the latter paper does not describe the running time of its algorithm, beyond saying that it is fast. An excellent survey of algorithms in number theory is H. W. Lenstra, Jr., "Algorithms in algebraic number theory" (Bulletin of the American Mathematical Society, v. 26 (1992), 211-244). Although it was written 25 years ago, still this is well worth reading.

$\endgroup$

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.