How to nicely extend finite field?

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:

1. randomly choose a monic polynomial $f(x)$ of degree $d$ (i.e. $x^d + \ldots$)
2. check if it is irreducible, if not, go to 1
3. 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.

migrated from cstheory.stackexchange.comJul 2 '11 at 4:40

This question came from our site for theoretical computer scientists and researchers in related fields.

• Handbook of Cryptography is your friend. There are several algorithms for efficient implementations of finite field arithmetic there. You may or may not benefit from the use of an optimal normal basis. I'm not up to date with what algorithms are best for computing the Weil pairing, so I added a couple of tags to attract more knowledgeable people. – Jyrki Lahtonen Jul 2 '11 at 5:59

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.