5
$\begingroup$

I asked this question in Math SE too, but I have since modified it to make it more suited here. Also, in hindsight, the question itself was more algorithmic and was a better fit here. https://math.stackexchange.com/questions/1844975/dependence-of-algebraic-elements-in-a-finite-field

Lets work over the finite field $\mathbb{F}_p$ for a prime $p$. Consider a monic irreducible polynomial $f(X)=X^3+aX^2+bX+c$ in $\mathbb{F}_p[X]$. Let $x$ be a root of $f(X)=0$ (say, in the closure of $\mathbb{F}_p$). Consider another different monic irreducible polynomial $g(Y)=Y^3+AY^2+BY+C$ in $\mathbb{F}_p[Y]$. Let $y$ be a root of $g(Y)=0$ again in the same closure.

Now we know that the field $\mathbb{F}_{p^3}$, realized explicitly as the extension $\mathbb{F}_p[X]/<f(X)>$ or $\mathbb{F}_p(x)$ contains a root (all three distinct roots, actually) of the irreducible $g(Y)$. This is because $\mathbb{F}_p(x)$ is the splitting field of $X^{p^3}-X$ which includes $g(X)$ as a factor. So we know that the root $y$ can be expressed as $$y=\alpha x^2+ \beta x +\gamma$$ for some $\alpha, \beta, \gamma \in \mathbb{F}_p$.

My question is: Is there an efficient algorithm that given as input the prime $p$ and the irreducible polynomials $f$ and $g$, computes $(\alpha,\beta,\gamma)$ as output? Though in my question, I am first interested in degree $3$, the same problem arises for higher degree too. This is easy to do when $f$ and $g$ are quadratic, as we can use specific properties of quadratic residues.

Of course, since we know that such a solution $(\alpha,\beta,\gamma)$ exists, we can simply substitute $\alpha x^2+ \beta x +\gamma$ for $Y$ in $g(Y)=0$ and solve the equation. But is there a better way?

The converse problem, of finding the irreducible which has $\alpha x^2+ \beta x +\gamma$ as a root can be solved simply by elimination, and the answer is simply a resultant polynomial. So considering that this converse problem has a neat construction, I was hoping that the above problem also has some neat algebraic formulation or efficient algorithmic solution.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.