My research and investigations

Finite Fields 2

The applications of the theory of finite fields (see here) depend on finding primitive polynomial of the field. This is due to the fact that a root of the primitive polynomial can act as a generator of the whole finite field.

My own presentation of this topic can be found here (click Primes for Random, then Simple Machines), showing how primitive polynomials underlie the construction of LFSRs for pseudo-random number generation.

In 1967, Elwyn Berlekamp invented an algorithm for decoding BCH codes, which is a type of polynomial code based on primitive polynomials of finite fields. Later James Massey simplified the algorithm, and recognized its application to LFSR which is also based on primitive polynomials of finite fields. Their algorithm is now known as Berlekamp-Massey algorithm.

My plan for the project work on this topic is to do the following:

  1. Formalize elementary field theory from its axioms, based upon a finite set.
  2. Extend this formalization to include the primitive polynomials of finite fields.

With these tools, I can try to prove the Berlekamp-Massey algorithm. I am now studying a Java applet that demonstrates this algorithm.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: