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.

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.

share|improve this question
    
"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
1  
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
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
add comment

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\:$).

share|improve this answer
add comment

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.