# 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

## 1 Answer

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.

-
Wait a minute - you mean, Jyrki isn't just an alternate spelling of joriki? –  Gerry Myerson Sep 8 '11 at 11:40
@Gerry: No, one is Finnish and the other is Japanese :-) –  joriki Sep 8 '11 at 11:45
:-) :-) I don't know, whether the pronounciations would be similar though? My first name shares the first syllable with German 'Jürgen', and (according to my experience) is unpronouncable by people whose exposure is to English/Spanish/French only. Given that joriki is a Japanese name I may need to revise the way I mentally pronounce it <insert an emoticon indicating headache>. –  Jyrki Lahtonen Sep 8 '11 at 12:01
@Jyrki: It's not a Japanese name; it's a Japanese word that I use as a name :-) (As the White Knight might say, "that's what the name is called" :-) Here's what it means: the-wanderling.com/joriki.html. –  joriki Sep 8 '11 at 12:08
@joriki: Thanks. Sounds interesting! Doesn't really help me to pronounce it, though :-)? Other than that I think I know how the 'ki'-syllable is pronounced. –  Jyrki Lahtonen Sep 8 '11 at 12:23