# Converting From One Representation of a Field Element to Another

Let $A \subseteq B \subseteq C$ be fields and let $\alpha$, $\beta$, $\gamma$ be such that $A(\alpha) = B$, $B(\beta) = C$, $A(\gamma) = C$. Assume $B$ and $C$ have finite degree over $A$.

Let $m(\alpha,A)$ be the minimal polynomial of $\alpha$ over $A$, let $m(\beta,B)$ be the minimal polynomial of $\beta$ over $B$, let $m(\beta,A)$ be the minimal polynomial of $\beta$ over $A$, and let $m(\gamma,A)$ be the minimal polynomial of $\gamma$ over $A$.

Let $c \in C$. We have, on the one hand, $$c=\sum_{i = 1}^{[C:B]} b_i \beta^{i-1}, \quad b_i \in B$$ $$b_i=\sum_{j = 1}^{[B:A]} a_{ij} \alpha^{j-1}, \quad a_{ij} \in A$$ and on the other hand $$c=\sum_{k = 1}^{[C:A]} c_k \gamma^{k-1}, \quad c_k \in A$$ We also have $$\gamma = \sum_{i = 1}^{[C:B]} d_i \beta^{i-1}, \quad d_i \in B$$ $$d_i=\sum_{j = 1}^{[B:A]} e_{ij} \alpha^{j-1}, \quad e_{ij} \in A$$ If the polynomials $m(\alpha,A)$, $m(\beta,B)$, $m(\beta,A)$, $m(\gamma,A)$ and the numbers $a_{ij}$, $e_{ij}$ are known explicitly, how can I calculate the $c_i$?

ADDED: Now that Joriki and Jyriki have helped me to formulate the problem correctly, I see the solution is not so hard. Since $$\gamma = \sum_{i = 1}^{[C:B]} \sum_{j = 1}^{[B:A]} e_{ij} \alpha^{j-1}\beta^{i-1}$$ we can find numbers $f_{ijk}$ such that $$\gamma^{k-1} = \sum_{i = 1}^{[C:B]} \sum_{j = 1}^{[B:A]} f_{ijk} \alpha^{j-1}\beta^{i-1}$$ by using the polynomials $m(\alpha,A)$, $m(\beta,B)$ to express large powers of $\alpha$ and $\beta$ in terms of smaller powers. Then $$c = \sum_{i = 1}^{[C:B]} \sum_{j = 1}^{[B:A]} a_{ij} \alpha^{j-1}\beta^{i-1}$$ and also $$c = \sum_{k=1}^{[C:A]} c_k \left( \sum_{i = 1}^{[C:B]} \sum_{j = 1}^{[B:A]} f_{ijk} \alpha^{j-1}\beta^{i-1} \right) = \sum_{i = 1}^{[C:B]} \sum_{j = 1}^{[B:A]} \left( \sum_{k=1}^{[C:A]} c_k f_{ijk} \right) \alpha^{j-1}\beta^{i-1}$$ Therefore $$a_{ij} = \sum_{k=1}^{[C:A]} c_k f_{ijk}$$ So we are reduced to solving this system of system $[C:A] = [C:B] \cdot [B:A]$ linear equations for the $c_k$.

-
With some difficulty, I think. Take a fairly simple example. Let $A$ be the rationals, $\alpha=\sqrt2$, $\beta=\sqrt3$, $\gamma=\sqrt2+\sqrt3$. You have $c=a_{11}+a_{12}\sqrt2+a_{21}\sqrt3+a_{22}\sqrt6$, and you want $c=c_1+c_2(\sqrt2+\sqrt3)+c_3(\sqrt2+\sqrt3)^2+c_4(\sqrt2+\sqrt3)^3$. Expressing the $c_i$ in terms of the $a_{ij}$ (and the minimal polynomials) looks mildly unpleasant. – Gerry Myerson Sep 8 '11 at 6:30
I would have thought that you can't, since there may be several values of $\gamma$ with the same $A(\gamma)$ and $m(\gamma,A)$ that will generally have different $c_i$? For example, consider $A=\mathbb Q$, $\alpha=1$, $\beta=\sqrt2$ and $\gamma=\pm\sqrt2$. Then $A(\gamma)=\mathbb Q(\sqrt2)$ and $m(\gamma,A)=x^2-2$ for both signs, but the sign of $c_2$ is flipped. – joriki Sep 8 '11 at 6:46
@Gerry Unpleasant or not, I need to find an algorithm do it. – maxpower Sep 8 '11 at 9:20
@maxpower: I don't understand. How do the $a_{ij}$ help? They're the same for both signs in my example. – joriki Sep 8 '11 at 9:29
@maxpower: I agree with joriki. The problem specification must include a way of identifying the element $\gamma$ in terms of $\alpha$ and $\beta$. Another example would be $\alpha=\sqrt2$, $\beta=i$, $\gamma$ any primitive eighth root of unity. All four sign combination are possible in $\gamma=\pm\alpha(1\pm\beta)/2$ in that all those numbers share the same minimial polynomial $x^4+1$. Unless you know which combination is $\gamma$, the problem cannot be solved. – Jyrki Lahtonen Sep 8 '11 at 9:44

The $c_i$ are not determined by the given data. Different values of $\gamma$ can lead to identical $A(\gamma)$ and $m(\gamma,A)$ but different values of $c_i$, as in the examples given in comments by Jyrki and me.