Better Pseudo-Random Sequences

The sequence above is too simple, but with just a tiny modification, it can be made much more interesting. The following sequence can work quite well.

Choose a (usually large) prime number $p$ and two integers $a$ and $c$. In addition, choose a ``seed'', or starting number for the random sequence which we will call $X_0$ such that $0 <= X_0 < p$. Here is the formula for $X_i$, if $i>0$:

$$X_i = (aX_{i-1} + c) ({\rm mod}\ p).$$

So, for example, if $p=16139$, $a = 91$, and $c = 541$, and we begin with $X_0 = 11111$, we generate the following sequence:

$$\begin{eqnarray*} X_0 &=& 11111 \\ X_1 &=& (91\cdot 11111 + 541) ({\rm mod}\ 16... ... 4856 \\ X_5 &=& (91\cdot 4856 + 541) ({\rm mod}\ 16139) = 6684 \end{eqnarray*}$$

which you can continue as long as you want. The first pseudo-random numbers in this sequence are: 11111, 11024, 3107, 8915, 4856, 6684. Of course the sequence has to cycle in $p$ or fewer steps.

As an exercise, try to decode the following message based on $p=16139$, $a = 91$, and $c = 541$, but with the starting value $X_0 = 0$. We will use the random sequence in the same way we did above--we converted our message to numbers between 10 and 99 using the table in Section 5, then we added successive keys and took the result modulo 100. Here is the resulting encoded message:

23, 52, 85, 91, 15, 06, 53, 61, 30, 72, 23

To get you started, the first number in the sequence is zero, so $X_0 = 0$, so the first number decodes as $(23-0) ({\rm mod}\ 100) = 23$, so the first letter in the message is ``M''. Then

$$X_1 = (91\cdot X_0 + 541) ({\rm mod}\ 16139) = 541 ({\rm mod}\ 16139) = 541,$$

so the second letter is $(52-541)({\rm mod}\ 100) = 11$, so the second letter is ``A''. Continue in the same way.