A source of ``random'' numbers if often needed to accomplish programming tasks. The reasons for this are varied and sometimes surprising. The programming task might simple be to produced a display of randoming flashing lights. Often random numbers are added to signal to increase the amount noise. This is beneficial in picture signals since very clean digital images have a number of artifacts including jagged lines and noticable contours on smoothly shaded surfaces. Making the signal noisy hides these artifacts from the eye, without really damaging the underlying information.

Since computers act entirely predictably, it is not possible for a computer to generate truely random numbers. Inside, we dream up processes which produce a stream of numbers which look random even though they follow an entirely predictable pattern. These numbers are called pseudorandom. There are many pseudorandom number generators, some of which are extremely sophisticated. Encryption of data, for example, depends on pseudorandom number generation for which finding any pattern in the number stream is extremely difficult. Since almost everyone's financial security and privacy depends on the quality of these pseudorandom number generators, you can imagine how carefully the areas has been studied!

Our pseudorandom number generator will not be of this quality. It is a simple shift register where the vacated bit of is filled with the exclusive-or of two other bits in the shift register.

Here is a 4 bit shift-register pseudorandom number generator:

+----->(+)-----------+ | | | | +---+---+---+---+ | +-| 4 | 3 | 2 | 1 |<-+ +---+---+---+---+At each time step:

- Bits 3 and 2 are combined by exclusive-or.
- The register is shifted 1 step to the left.
- The result of the exclusive-or is entered into bit 0.

0001 0010 0100 1001 0011 0110 1101 1010 0101 1011 0111 1111 1110 1100 1000 0001The pattern repeats endlessly. The length of the pattern in 15 different bit combinations. This is the maximum possible. There are at most 16 different bit combinations in a 4 bit register (2 to the power 4) however the combination

It is **very important to note** that not every choice of two bits
to exclusive-or will work equally as well. Here is a bad choice for
the 4 bit shift-register:

+--------->(+)-------+ | | | | +---+---+---+---+ | +-| 4 | 3 | 2 | 1 |<-+ +---+---+---+---+ BAD CHOICEThis bad choice gives a shorter sequence of bit patterns:

0001 0010 0101 1010 0100 1000 0001

The previous section gave an illustration of a pseudorandom generator for 4 bits and showed that it was possible to get the maximum length sequence of 15 = (2 to the power 4) - 1 by tapping at bit 3, but not by tapping at bit 2. It turns out that bit 1 is also OK to tap.

We now generalize to `n` bits tapping at bit location
`m`. We give a table for the selection of `m`
such that the resulting sequence is of length `(2 power n)-1`.
Note that each entry is actually two entries. It
can be proven using mathematics
that if `m` is a good choice for a given
`n`, then so is `n-m`. For example: in the
previous section we showed that `n=4` and `m=3`
was a good choice. Then so is `m=4-3=1`.

The shift-register pseudorandom number generators are calculating the successive powers of an unknown x in a finite number field called the Galois (gall-wah) of order 2 to the n. To understand, first consider the simplist finite number field. Take a prime p and consider the integers mod p. They are 0, 1, 2, etc. up to p-1, with addition and multiplication mod p. Since p is prime (and only if p is prime!) with the exception of 0, for each x there is a y such that x*y = 1 mod p. That is, each number except zero has an inverse mod p without resorting to the invention of fractions.

**Example:** For the prime p=7,

- 1*1 = 1 mod 7; so 1 is its own inverse, as usual.
- 2*4 = 1 mod 7; the inverse of 2 is 4, and of 4 is 2. So "one-half" is actually 4, and "one-quarter" is actually 2.
- 3*5 = 1 mod 7: the inverse of 3 is 5, and of 5 is 3.
- 6*6 =1 mod 7; so 6 is its own inverse, because it acts like -1 mod 7, and (-1)*(-1) should equal 1.

**Exercise:** Make a table of inverses for p=11.

The next step is to find a number and take its successive powers mod p and see what happens. For a good choice of number the successive powers will cycle through all the possible numbers mod p in a pseudorandom way. This is the basis of the presented shift-register pseudorandom number generator.

**Example:** For the prime p=7, the number m=3 cycles nicely:

- 3*3 = 2 mod 7; 3 to the power 2.
- 2*3 = 6 mod 7; 3 to the power 3.
- 6*3 = 4 mod 7; 3 to the power 4.
- 4*3 = 5 mod 7; 3 to the power 5.
- 5*3 = 1 mod 7; 3 to the power 6.
- 1*3 = 3 mod 7; 3 to the power 7.
- and it begins all over again.

**Exercise:** Find a number m such that m to the 2, 3, 4, ..., 11 cycles
through all 10 non-zero values mod the prime p=11.

Although these example illustrate conceptually how our shift-registers work, the "numbers" which are stored in the shift-registers, and the multiplication by successive powers, might be unusual to the beginner in mathematics.

The numbers used here are the polynomials with coefficients mod 2. Think of these polynomials as the integers, and we take them modulo another polynomial, which also must be prime, that means a polynomial which does not factor. The coefficients of the polynomial are mod 2, that means that the values for the coefficients are either 0 or 1, and 1+1=0. Each location in the shift-register is the coefficient for a power of x, and shifting to the left is multiplication by x. The feedback using the exclusive-or does the modulus arithmetic. Just as going over p in the integers mod p wraps back to a smaller integer, shifting-out of the highest bit in the shift-register is making x too high a power, and it wraps back to a combination of lower power x's. The choice of which bits to include in the exclusive-or is a choice of polynomial for the modulus, and the table given in the previous section indicates which polynomials are prime.

**Example of polynomials:** Here are **all**
the polynomials with coefficients mod 2 for small degree:

- Degree 0: 1 or 0, all the constant polynomials.
- Degree 1: x or x+1, all the linear polynomials.
- Degree 2: x^2, x^2+1, x^2+x, x^2+x+1, all the quadratic polynomials.

**Example of addition:** Adding polynomials mod 2 is the same
as adding "normal" polynomials except that the coefficient arithmetic
is mod 2, that is 1+1=0.

- (x+1) + x = 1, because 2x is the same as 0x.
- (x^2+1) + (x+1) = x^2 + x, because 1+1 = 0.

**Example of multiplication:** Multiplying polynomials mod 2 is
the same as multiplying "normal" polynomials except the required additions
are done mod 2, as above.

- (x+1) * x = x^2+x.
- x*x = x^2.
- (x+1)*(x+1) = x^2+1, because the middle term 2x is the same as 0.

It is important to keep track of two types of modular arithmetic which are being done simultaneously: the coefficients are mod 2, but the polynomials are also viewed modulo a given polynomial Q. Making the parallel with integers mod a prime, after arithmetic with the polynomials it is reduced mod Q by dividing by Q and considering the remainder as the result of the arithmetic.

In our situation, it is easy to use repeated subtraction rather than division (which is the same thing) because the only operation we will do is multiplication by x. So the polynomials only get a very little bit larger, and can be reduced if need be by a single subtraction.

**Example of modular arithmetic:** Let Q=x^4+x+1. Then
reduce each polynomial by taking its remainder after division by Q.
If the polynomial to be reduced has no term higher than x^3, then
leave it alone. If it has a term x^4, then add Q to the polynomial.
This is legal since mod Q the polynomial Q acts as zero, so adding
it does not change the value. The effect is to replace x^4 by x+1.
We will not worry about x^i, for i greater than 4, because our
shift-register never generates such results.

- x+1 stays the same mod x^4+x+1.
- x^4+1 = (x^4+1) + (x^4+x+1) = x (mod x^4+x+1), because 2x^4 and 2x are zero.
- (x^3+1)*(x+1) =(x^3+1)*x + (x^3+x)*1 = (x^4+x)+(x^3+x) = (x^4+x^3) + (x^4+x+1) = x^3+x+1 (mod x^4+x+1).

We began our discussion with the following 4 bit shift-register:

+----->(+)-----------+ | | | | +---+---+---+---+ | +-| 4 | 3 | 2 | 1 |<-+ +---+---+---+---+In our table, this example is

We will demonstrate the arithmetic in full by showing side by side the bit patterns according to shifting and exclusive-or, and the successive powers of x with reduction by the polynomial x^4+x+1, and you will see that the two procedures continuously correspond:

0001 is x 0010 is (x)*x = x^2 0100 is (x^2)*x = x^3 1001 is (x^3)*x = x^4 = x+1 (mod x^4+x+1) 0011 is (x+1)*x = x^2+x 0110 is (x^2+x)*x = x^3+x^2 1101 is (x^3+x^2)*x = x^4+x^3 = x^3+x+1 (mod x^4+x+1) 1010 is (x^3+x+1)*x = x^4+x^2+x = x^2+1 (mod x^4+x+1) 0101 is (x^2+1)*x = x^3+x 1011 is (x^3+x)*x = x^4+x^2 = x^2+x+1 (mod x^4+x+1) 0111 is (x^2+x+1)*x = x^3+x^2+x 1111 is (x^3+x^2+x)*x = x^4+x^3+x^2 = x^3+x^2+x+1 (mod x^4+x+1) 1110 is (x^3+x^2+x+1)*x = x^4+x^3+x^2+x = x^3+x^2+1 (mod x^4+x+1) 1100 is (x^3+x^2+1)*x = x^4+x^3+x = x^3+1 (mod x^4+x+1) 1000 is (x^3+1)*x = x^4+x = 1 (mod x^4+x+1) 0001 is (1)*x = x

On the other hand, the following shift-register does not work as we wish:

+--------->(+)-------+ | | | | +---+---+---+---+ | +-| 4 | 3 | 2 | 1 |<-+ +---+---+---+---+ BAD CHOICEFor this example, where

0001 is x^2 0010 is (x^2)*x = x^3 0101 is (x^3)*x = x^4 = x^2+1 (mod x^4+x^2+1) 1010 is (x^2+1)*x = x^3+x 0100 is (x^3+x )*x = x^4+x^2 = 1 (mod x^4+x^2+1) 1000 is (1)*x = x 0001 is (x)*x = x^2

So what's the difference between the two examples? The polynomial x^4+x+1 is prime, but the polynomial x^4+x^2+1 is not (where we continue to assume the coefficients are mod 2). Here is the factors of x^4+x^2+1,

(x^2+x+1) * (x^2+x+1) = x^4 + 2x^3 + 3x^2+ 2x + 1 = x^4 + x^2 + 1 (coefficients mod 2)In the example of the integers mod 7, we found an inverse for every integer except 0, and this depended on the fact that 7 is prime. In any cycle of numbers generated by successive powers, every number on in the sequence must has an inverse. For instance, if x has inverse y then x^2 has inverse y^2, and so on. So in order to have the sequence contain all numbers except 0, all numbers except zero must have inverses, and so the modulus must be prime.

Pseudorandom numbers can be generated by a simple shift-register by taking successive powers of x in the field of polynomials with coefficients mod 2 modulo a prime polynomial. This exotic sort of arithmetic is actually very simple in reality: the polynomials are represented in an n-bit shift-register where each bit gives the coefficient 0 or 1 for x^i; multiplication by x is a left shift; and reduction modulo the polynomial Q=x^n+x^k+1 is accomplished with an exclusive-or of the overflow bit into the bit which corresponds to x^k (the least significant in the shift register) along with the implied shifting of the overflow bit into the bit which corresponds to x^0.

To get the maximum length cycles, Q must not factor as a polynomial
with coefficients in mod 2, and x must cycle through all 2^n-1 non-zero
polynomials mod Q. A table is given which shows what `m`
values achieve this goal.

The arithmetic on the polynomials with coefficients mod 2, taken modulo a prime polynomial Q is called the Galois Field on 2^n elements and is used often in coding, error correction, computer science, and so on. Here we have one example of its use.

*Copyright (c) 1997 Burton Rosenberg. All rights reserved.*

*Last modified: Tue Oct 28 13:52:53 EST 1997*
* Fri Sep 28 2018*