## Generation of pseudorandom numbers by a shift register

Burton Rosenberg
28 October 1997

### Introduction

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.

### Presentation

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

```   +----->(+)-----------+
|       |            |
| +---+---+---+---+  |
+-| 4 | 3 | 2 | 1 |<-+
+---+---+---+---+
```
At each time step:
1. Bits 3 and 2 are combined by exclusive-or.
2. The register is shifted 1 step to the left.
3. The result of the exclusive-or is entered into bit 0.
Here is the pattern of bits, starting with 0001:
```   0001
0010
0100
1001
0011
0110
1101
1010
0101
1011
0111
1111
1110
1100
1000
0001
```
The 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 0000 is not a real possibility, since if the register is ever at 0000 it will remain forever at 0000.

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 CHOICE

```
This bad choice gives a shorter sequence of bit patterns:
```   0001
0010
0101
1010
0100
1000
0001
```

### Table of good shift-register pseudorandom generators

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.

n m or n-m 2 to n -1
3 1 7
4 1 15
5 2 31
6 1 63
7 1, 3 127
8 none-
9 4 511
10 3 1,023
11 2 2,047
12 none -
13 none -
14 none -
15 1, 4, 7 32,767
16 none-
173, 5, 6 131,071
n m or n-m 2 to n -1
18 7 262,143
19 none -
20 3 1,048,575
212 2,097,151
221 4,194,303
235, 98,388,607
24none -
25 3, 7 33,554,431
26 none -
27 none -
28 3, 9, 13 268,435,455
29 2 536,870,911
30 none -
31 3, 6, 7, 13 2,147,483,647
32 none -
33 13 8,589,934,591
From: Branko Soucek, Minicomputers in Data Proc. and Simulation, Wiley-Interscience,1972.

### The theory

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.
Our pseudorandom number sequence is 2, 6, 4, 5, 1, 3.

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.
Note well that the only coefficients allowed are 0 or 1.

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

### Application of the theory to shift-registers

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

```   +----->(+)-----------+
|       |            |
| +---+---+---+---+  |
+-| 4 | 3 | 2 | 1 |<-+
+---+---+---+---+
```
In our table, this example is n=4 and m=3. Each pattern of bits in the shift register corresponds to a polynomial with coefficients mod 2. The mapping is:
BitPower of x
1x^1
2x^2
3x^3
4x^0
For instance, 0101 is polynomial x^3+x. Because m=3, the polynomial chosen for modular arithmetic is Q=x^4+x+1. Each shifting left is taking x^i to x^(i+1). The overflow of (x^3)*x=x^4 is reduced mod x^4+x+1 by changing the x^4 into x+1. That is, bit 3 (which represents x^3) becomes bit 4 (which represents x^0=1) and also bit 1 (which represents x^1) but only if the current bit 4 was 0 - else the result is adding x to (1)*x and therefore there should be no x term in the result.

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 CHOICE

```
For this example, where m=2, the table mapping bits to coefficients of x^i is:
BitPower of x
1x^2
2x^3
3x^0
4x^1
And the idea is that x^4 is replaced by 1 and x^2, if there isn't already an x^2 shifting in from bit 4 (which represents x^1). Hence the polynomial to reduce by is x^4+x^2+1. Here's the result, giving corresponding bit manipulations and polynomial arithmetic manipulations:
```   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.

### Conclusion

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