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
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
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...
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 (??).