Prev: SigLib
Next: FFT Windowing and Transmit Pulse Shaping
From: Larry D'Anna on 11 Aug 2010 15:46
* Jaco Versfeld (jaco.versfeld(a)gmail.com) [100429 06:56]:
> Hi There,
>
> (My apologies for cross-posting)
>
> The following polynomial is used to create a "Galois field" GF(2^8)
> which is specified in the Advanced Encryption Standard (AES): p(x) =
> x^8 + x^4 + x^3 + x + 1.
>
> However, I checked the polynomial (quickly using Matlab) whether it is
> primitive. It turns out not to be primitive, but still irreducible (I
> haven't yet confirm this for myself, though).

I just checked it in sage, it is irreducible.

> According to my knowledge, you need a primitive polynomial in order to
> construct a "proper" Galois field (or extended Galois field).

That's not true. If p(x) is any polynomial at all in GF(2)[x], then you have a
finite ring R = GF(2)[x]/(p(x)), with size(R) = 2^deg(p). R will be a field if
and only if p(x) is irreducible. So in this case R is a finite field with 2^8
elements, and since all finite fields with the same cardinality are isomorphic,
R is GF(2^8).

Now because we've constructed R explicitly, there one particularly special
element of R (besides 0 and 1), namely 'x'. You can start raising x to powers

1 x x^2 x^3 ....

And then you might wonder how long does this sequence continue before it loops
around? Will I get every nonzero element of R in the sequence? This is where
primitivity comes in. A primitive polynomial is just a polynomial that makes
every nonzero element of R a power of x. So you don't need the polynomial to be
primitive to construct a finite field, but it might be convenient if it were.


--larry
 | 
Pages: 1
Prev: SigLib
Next: FFT Windowing and Transmit Pulse Shaping