2

If there a canonical representation of finite fields $\Bbb F_{p^n}$ for $n>1$?

By canonical I mean that if I were to say to someone else "this bunch of bits represents an element of $\Bbb F_{p^n}$", he'd be able to find that element without needing more information.

In the case $n=1$, it's obvious that the bunch of bits simply represents an integer $a$ less than $p$. And the element is $a+(p)$ in $\Bbb Z / p\Bbb Z$.

But for $n>1$, I didn't see any canonical representation and since we may compute the splitting fields differently, we could end up with isomorphic but different fields. And then the binary representation wouldn't represent the correct element.

Obviously, you could add some order on the polynomials and use that to make sure you get the same representation but that seems rather arbitrary. Hence my question.

xavierm02
  • 7,495
  • I suspect that it is impossible. In any case, your representation must include $p$ and $n$. Including also $a$ and $b$ of $X^n+ax+b$ or choosing the first irreducible $X^n+ax+b$ in the loop FOR b=1; FOR a=0 ... isn't terribly inconvenient. – Martín-Blas Pérez Pinilla May 15 '14 at 06:44
  • It's not terribly inconvenient. But since I want to use Shamir secret sharing, it triples the size of parts... So since I'm going to write those on paper, I'd rather keep them short :) $p=2$ and $n=$"number of bits" and can be determined just by looking at the paper (because I'll leave non-significant $0$s). But I think it'll take the smallest $p>2^n$ that's prime. – xavierm02 May 15 '14 at 08:49

1 Answers1

1

The finite field $F_{p^n}$ is a splitting field of the polynomial $f(x) =x^{p^n}-x$ over $\mathbb{Z}_p$. That determines $F_{p^n}$ up to a field isomorphism.

It's ok that there are $F_{p^n}$ that are set-theoretically different but isomorphic, just like there are different ways of defining $\mathbb{R}$. Is "Dedekind cut" canonical or "Completion of $\mathbb{Q}$" canonical or what have you? What you call "canonical representation" is a choice.

mez
  • 10,497
  • 1
    I wanted to represent my elements of $\Bbb F_{p^n}$ by polynomials of $\Bbb F_p[X]$. And I assumed there would be many ways to do so. – xavierm02 May 14 '14 at 10:19
  • @xavierm02 Let $a\in \mathbb{F}{p^n}$, then you can "represent" $a$ with its irreducible polynomial, which is of the form $f_a(x) = (x-a)^{p^k}$ where $1\le k\le n$ and $a\in\mathbb{F}{p^k}\hookrightarrow \mathbb{F}_{p^n}$. – mez May 14 '14 at 13:57
  • Will this polynomial have coefficients in $\Bbb F_p$? It feels like it should be but it's not that obviously. If you apply the Frobenius automorphism, you get $X^{p^k}\pm a^{p^k}$ and unless I'm mistaken, that's $X^{p^k}\pm a$. How does that help representing $a$? Or should I extend the polynomial and it'll magically have coefficients in $\Bbb F_p$? – xavierm02 May 14 '14 at 14:18
  • @xavierm02 It's not true $a^{p^k} = a$. Put it this way, two distinct elements in $\mathbb{F}{p^n}$ have different irreducible polynomials in $\mathbb{Z}_p[x]$. Therefore the elements of $\mathbb{F}{p^n}$ and the set of irreducible polynomials over $\mathbb{Z}p[x]$ that splits $\mathbb{F}{p^n}$ are bijective. In this sense we can represent elements by its irreducible polynomial over $\mathbb{Z}_p[x]$. – mez May 14 '14 at 18:10
  • Hm. Why is it not true? This wikipedia page seems to say it is http://en.wikipedia.org/wiki/Finite_field#Cyclic – xavierm02 May 14 '14 at 18:18
  • And, assuming I want to do some computation where I need to represent the elements as polynomials modulo another polynomial. How do I get from those ireducibles polynomials to my element? I just try all elements and the only one on which the evaluation of the polynomial yields $0$ is the good one? – xavierm02 May 14 '14 at 18:22
  • @xavierm02 First, $1\le k<n$. If you want to use fermat's theorem you need to check that $a$ has order $p$, which might not be true. I still don't understand what you want to represent. Try to formulate your question more clearly. – mez May 14 '14 at 18:27
  • @xavierm02 If you want to "find" the irreducible polynomial of an element, take the monic polynomial of least degree that have that element as a root. – mez May 14 '14 at 18:28
  • 1
    I was wondering how to find it algorithmically but I found papers explaining that. And I know that $k<n$ but you said $a\in\Bbb F_{p^k}$. Anyway, it's far too complicated for what I had in mind so I'll just take a $\Bbb F_{p'}$ with $p'>p^n$ and prime. – xavierm02 May 14 '14 at 23:28