Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

migrated from cstheory.stackexchange.com Jul 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

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
You're right. Fortunately, extending from GF(p^d) to GF(p^{nd}) is also fine for me. So thanks! –  Jasiu Jul 2 '11 at 1:20

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.