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

Improve this question
$\endgroup$
6
  • 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 at 14:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.