I'm working on an implementation of Miller's algorithm that computes the Weil pairing (elliptic curves, cryptography). In order to do that, I have to implement finite fields.
So far I have managed to implement $GF(p^d)$ as follows:
- randomly choose a monic polynomial $f(x)$ of degree $d$ (i.e. $x^d + \ldots$)
- check if it is irreducible, if not, go to 1
- implement $GF(p^d)$ as ring of polynomials $GF(p)[x]$ modulo $f(x)$
Now, what I still need is to extend $GF(p^d)$ into $GF(p^{d+1})$ in a way that will let me easily translate elements of $GF(p^d)$ into $GF(p^{d+1})$. Can this be done and how?
Disclaimer: perhaps this question belongs more to MathOverflow than here, but what I'm looking for is definitely an algorithm, because I don't think a closed formula exists. So that's why I ask here.
This can't be done; the field $GF(p^d)$ isn't a subfield of the field $GF(p^{d+1})$ for any $d\gt1$. Probably the easiest way to see this is via the multiplicative group of the field; since the multiplicative group of a finite field is cyclic, there's some element of order $p^d-1$ in $GF(p^d)$. But no element in $GF(p^{d+1})$ can have this order, because it doesn't divide $p^{d+1}-1$. You can embed $GF(p^d)$ in $GF(p^{nd})$ for each $n$ by treating the latter as a vector space of dimension $n$ over the former, but that's the best you can do.