[Noisebridge-discuss] Help with finite fields.

[Ben Kovitz]

On Fri, Dec 4, 2009 at 1:04 AM, Jason Dusek <jason.dusek at gmail.com> wrote:
>  I am reading this page:
>
>    http://en.wikipedia.org/wiki/Finite_field
>
>  The notation is very confusing. What is meant by this?
>
>    (Z/2Z)[T]/(T²+T+1)
>
>  Most of the rest of them are just like that.

It definitely takes some getting-used-to.

In group theory, / means "factor group".  G/N means "The group that
you get if you take N (a normal subgroup of G) and make it the
identity ('zero') element.  Each element in this new group is actually
a subset of elements of G (a "coset", as they say).  Any of the
elements in G can serve as a 'representative' of its element in G/N.
G/N's operation is the same operation as that of G, with this
modification (assuming + is the operation): aN + bN = (a + b)N where
aN and bN are elements of G/N, and a and b are elements of G.  In
plainer English, that means that you perform G's operation on any
element (a 'representative') from aN and bN, and whatever element in G
you get is a representative of the coset that is the result in G/N."

Confused yet?  Factor groups are really not very complex, but that
abstract way of talking about them used to drive me nuts.  An example
or two might help.

Z means the integers.  2Z means the even integers.  The factor group
Z/2Z is the group that you get when you take the even integers as one
element and the odd integers are the other element.  It's a tiny
group, just two elements, called 2Z and 2Z+1.  Assuming addition is
the operation one has in mind, you would convert addition in Z into
addition in Z/2Z like this.  6 is a representative of 2Z, because 6 is
even.  5 is a representative of 2Z+1.  If you add 6 + 5, you get 11,
which is odd.  So, 2Z + 2Z+1 = 2Z+1.  If you pick any representatives,
you get the same answer.  Notice that 2Z functions as 'zero' in Z/2Z.
If you add something to it, you get what you started with.

In the article you're reading, Z/2Z actually refers to a factor ring,
not a factor group.  A ring is like a group, except there are two
operations (like addition and multiplication).  A field is a special
kind of ring, where you can always 'undo' multiplication (except
multiplication by zero).  A field basically behaves the way you expect
numbers to behave ordinarily.

The notation R[x] means "the ring of polynomials in x".  That is, all
the functions of the form ax^n + bx^(n-1) + ... + cx + d, where a, b,
c, d are all elements of R, and (typically) so is x.  In the place
where you found it, (Z/2Z)[T] *really* means (I'm translating loosely)
polynomials where the coefficients are 0 or 1 and the x's are
integers.  (Z/2Z)[T]/(T^2 + T + 1) means the factor ring resulting
from treating T^2 + T + 1 as the 'zero' of that ring of polynomials.

If you're just getting started with abstract algebra, you might play
with groups for a little while before coming back to rings and fields.
 Of course, a cool thing about learning in a hackspace is you can
start anywhere you like and follow any path you like. :)

What got you curious about this weird stuff?

Ben