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.