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.



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.