# Powers of $x$ as members of Galois Field and their representation as remainders

first question on math.stackexchange :)

I'm studying for a Cryptography - Communication Security exam, and it involves a certain quantity of number theory - finite field theory, so be warned: this is my first encounter with these topics, and you'll have to be extra-clear with me :)

I thought I was doing pretty well with the questions and exercises in $GF(4)$… then I hit $GF(8)$ and realized I'm still missing the point :(

I understand that to represent, let's say, $x^3$, the fourth element of $GF(8)$, I just take the result of the division of my irreducible polynomial of choice, let's say $x^3+x+1$, and I'm happy. I can then build addition and multiplication tables, and switch to and from a binary representation when it seems more convenient (e.g. when XORing with something else), and this also makes me happy.

But why do I start dividing $x^0$, $x^1$, $x^2$, etc.?
This sure seems like a sound idea when compared to “try some random polynomial“, but I can't figure why these are the candidates for being the members of the finite field? Why am I sure that this will generate all the elements?

Bonus question: $GF(4)$ seems to have a number of properties that are quite useful for manipulation. It seems obvious that $x+x \equiv 0$ in any $GF(2^n)$, but do $x^2 \equiv x+1$ or $x^3\equiv x^2+x\equiv 1$ always hold? Is this in any way dependent on the irreducible polynomial chosen? Are these predictable?

Please forgive me for any obvious error, and thanks in advance for any help.

-
"It seems obvious that x+x≡0 in any Galois Field" did you mean only fields of power of two? if not consider GF(3). –  anon Sep 1 '10 at 15:40
Be careful about the terminology. Forgive me if I'm wrong, I think that Galois field = finite field, so like muad has said GF(3) would be an example where x+x = 0 fails to hold. (Though it may not be of interest to cryptography stuff, I'm not sure) –  Soarer Sep 1 '10 at 16:12
it would be good if you specified what reference you're working from; in particular, what your definitions are. It is hard to explain anything until we know more about what you do and don't know. –  Qiaochu Yuan Sep 1 '10 at 16:28
Whoa yes, thanks @maud and @Soarer, I didn't specify, but I'm working only with powers of two. Will correct question stat. –  Agos Sep 1 '10 at 16:38

First: a Galois field is a finite field. A finite field will have $p^n$ elements for some prime $p$ and some positive integer $n$ (in fact, there is, up to isomorphism, one and only one finite field with $p^n$ elements). If a field has $p^n$ elements, then $x+x+\cdots+x=0$ ($p$ summands) for all $x$, and no smaller positive integer has that property; this is called the characteristic of the field. For fields of order a power of $2$, you do indeed have $x+x=0$ for all $x$, but not for any other size Galois fields. However, in computer science and cryptography there is some preference for working in fields of characteristic $2$, because they tend to be easier to represent and work with in computers (which themselves work in "characteristic $2$").

I'm not sure what you mean by "why do I start dividing $x^0$, $x^2$, $x^2$, etc.?". As you have probably seen, the field $GF(2^n)$ can always be described in terms of a monic polynomial $P(t)$ of degree $n$ that is irreducible over $GF(2)$. This amounts to constructing the field $GF(2)[t]/(P(t))$. What this tells you is that you have the smallest ring that contains $0$, $1$, and $x$, subject to the conditions $1+1=0$, $1\cdot 1=1$, and $P(x)=0$. Any element of this ring can be written as a polynomial expression in $x$ with coefficients $0$ or $1$, $q(x) = b_mx^m+\cdots + b_0$.

Now, because we are assuming that $P(x)=0$, using the division algorithm we can always write any polynomial $q(t)$ as $q(t)=P(t)b(t) + r(t)$, with $r(t)=0$ or $\deg(r)\lt \deg(P)=n$. Evaluating at $x$ and using the fact that $p(x)=0$, we get that $q(x)=r(x)$, so in fact every element in this ring can be written as a polynomial expression in $x$ of degree less than $n$. The expression is unique, because if $r(x)=s(x)$ with $r$ and $s$ of degree less than $n$, then $r-s$ would be a multiple of $P(t)$ (because the latter is irreducible), and degree considerations tell you that $r=s$.

So each element of $GF(2^n)$ can be written uniquely as $q(x)$ where $q$ has degree less than $n$. Choosing different polynomials amounts to choosing different representations for the elements, and so different rules for what $x^n$ will mean.

So: in order for $x^2=x+1$ to hold in your Galois field $GF(p^n)$, you must have that $x^2-x-1=0$, so the polynomial $P$ you picked must divide $x^2-x-1$, and so you must be either in $GF(p)$ or in $GF(p^2)$. Similarly, for $x^3=x^2+x=1$ to hold you would need to be in $GF(p)$ or $GF(p^2)$ in order for $x^2+x-1=0$ to hold; and whether it holds depends on the polynomial $P$ that you picked to define how $x$ behaves.

In summary: you divide by the polynomial so you can get a unique expression for each element in $GF(2^n)$ in terms of the distinguished element $x$ that helps you construct it (the behaviour of the element $x$ being determined by the polynomial). The condition $\alpha+\alpha=0$ will hold for every $\alpha$ in every Galois field of size $2^n$ for any $n$; but no power of $x$ smaller than $n$ will be expressible in terms of lower powers of $x$, and the expression of $x^n$ in terms of lower powers is determined by your choice of polynomial.

-
Thanks, very helpful and clear! –  Agos Sep 3 '10 at 14:42
"but no power of $x$ smaller than $n$ will be expressible in terms of lower powers of $x$" not sure about this. Does not $x^2=x \cdot x$ where $n>2$. –  ThomasMcLeod May 25 '11 at 15:42
@Thomas: "expressible" here means as an $\mathbb{F}_p$-linear combination of smaller powers, not products. –  Arturo Magidin May 25 '11 at 16:08

It appears that you may mistakenly believe that every element of your finite field is a power of $\rm x$. Here is a very simple counterexample: put $\rm\; f(x) = (x^5-1)/(x-1) = x^4 + x^3 + x^2 + x + 1 \;$, which is irreducible $\pmod 2$. Then $\rm\; (x-1) \: f(x) = x^5 - 1 \Rightarrow \rm x^5 \equiv 1 \pmod{f(x)}$. This implies that the powers of $\rm x$ generate only 5 elements, not all 15 nonzero elements of $\rm GF(2^4)$ constructed with $\rm f(x)$.

In fact there does exist an element whose powers generate all the nonzero elements of the finite field (said more technically: the multiplicative group is cyclic). Such generators are known as primitive elements. However, generally there is no simple closed-form known for such generators.

The reason that you didn't see this in $\rm GF(4)$ or $\rm GF(8)$ is because their multiplicative groups have prime order $3$ and $7,$ so every element $\ne 1,0 \:$ is a generator (by Lagrange's theorem the order of an element divides the order of the group which, being a prime $\rm p,$ forces the order to be $\rm p\:$ for elements $\rm \ne 1,0\:$).

-