Sun Aug 8 10:13:06 CEST 2010

More PRN sequences: 1/x as fractional or p-adic number.

What I'm looking for are binary sequences that are naturally periodic
and somehow "obvious".

An interesting place to look is the fractional digits of 1/x, where x
is some special number.  At some point the digits start repeating.

Apparently pseudo random noise generation is an application of Sophie
Germain primes[2].

A prime number p is a Sophie Germain prime if 2p + 1 is also prime.

( Instead of the fractional expansion, can we also use the p-adic
expansion? )

Constructing the bit sequence is done using long division.  The period
can be obtained from observing that in base b:

1 / (b^n - 1)  = 0.0...10...10...
                  n digits

For a number 1/q we find the smallest n such that

    q * x = b^n - 1

Here x is the repeated pattern in the fractional expansion of 1/q, one
period of the pseudo random number sequence we are interested in.  How
can we make sure that n is as large as possible?

In other words, find a q that maximises n, where n is the smallest
number such that q divides b^n - 1.

Rewriting it makes it a bit more clear.

          b^n = 1 + q * x   ->   b^n = 1 (mod q)

How to make n as large as possible?  Let's start with q a prime
number.  Then this becomes a statement about the multiplicative group
of the field Z/qZ, which has order q-1.  

The multiplicative group of a finite field is cyclic and commutative,
so completely determined by its order.

Now, when q is a Sophie Germain prime of the form 2p + 1 the
multiplicative group order is 2p.  There are 3 possible cycles in this
group, with periods 2, p, and 2p.  What needs to be verified to make
sure we have the maximal cycle length 2p is that b is a generator of
this cycle (b is a primitive element), meaning

        b^2 !=  1 mod q
        b^p !=  1 mod q

For b = 2 the first one is true when q > 3.  The second one can be
verified for given p and b, but probably also proven generally (??).

[1] http://en.wikipedia.org/wiki/Sophie_Germain_prime
[2] http://mathworld.wolfram.com/DecimalExpansion.html