Sun Aug 8 08:44:55 CEST 2010

Finite Field Automorphisms

A binary LFSR sequence ultimately comes from a cycle in the
multiplicative group of a finite field GF(2^n).  This is a unique
mathematical structure with a bunch of representatives that are all
isomorphic.  So, what does the automorphism group of a finite field
look like?

One place to look for some intuition is in Gold Codes[1].  This is the
only practical application I know where two sequences with different
generator polynomials are combined to form a new sequence with useful
properties.  Interesting properties of Gold codes:

  * Low autocorrelation (this is a "meaningless" property, as they are selected

  * The XOR (+) operation is closed

    PROOF:  Say s1(n) and s2(n) are LFSR sequences of the same lenght.
            A gold code is constructed as g(n) = s1(0) + s2(n).
            We then have 
              g(a) + g(b) 
            = s1(0) + s2(a) + s1(0) + s2(b)
            = s2(a) + s2(b)
            = ...  ???  (hmm... it seemed obvious - not awake yet)

A link I found about finite field automorphisms[3].  Time to finally
get into Galois Theory[4].

But what do I know?  It has to do with the structure of the
multiplicative group.  I would think that the symmetry group gets
larger if the multiplicative group is very composite.

So, which GF(2^n) have prime order multiplicative groups?  Are there
primes that look like 2^n-1?  Mersenne primes[7].

But is it really primes we're looking for, not maximally composite

[1] http://en.wikipedia.org/wiki/Gold_code
[2] http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=1054048
[3] http://everything2.com/title/automorphisms+of+finite+fields
[4] http://en.wikipedia.org/wiki/Galois_theory
[5] http://en.wikipedia.org/wiki/Safe_prime
[6] http://en.wikipedia.org/wiki/Strong_prime
[7] http://en.wikipedia.org/wiki/Mersenne_prime