4.5. Applications#

To be continued…

4.5.1. Pseudo-Random Numbers#

Randomly generating numbers is a crucial subroutine of many algorithms in computer science. Because computers execute deterministic code, it is not possible (without external influence) to generate truly random numbers. Hence, computers actually generate psuedo-random numbers.

The linear congruential method is a simple method for generating pseudo-random numbers. Let \(m\) be a positive integer and \(a\) be an integer \(2 \leq a < m\), and \(c\) be an integer \(0 \leq c < m\). A linear congruential method uses the following recurrence relation to define a sequence of pseudo-random numbers:

\[\begin{split} x_{n+1} = a\, x_n + c \ \textbf{ mod }\ m \\[1em] \end{split}\]

The initial condition of the recurrence realtion is called a seed of the random number generator.

If we let \(a = 4\), \(c = 3\) and \(m = 13\), the sequence with a seed of \(1\) is:

\[ (1, 7, 5, 10, 4, 6, 1, 7, 5, 10, 4, 6, 1, 7, 5, \ldots) \]

Notice that this sequence repeats after the first six elements. Linear congruence methods are always periodic. They repeat after a certain number of repetitions. However, with \(m = 13\), we might expect that the period be \(13\), since there are \(13\) integers in the range \(0, 1, \ldots, 12\).

For a linear congruence generator to have a maximum period, it needs several conditions. These conditions are given by the Hull–Dobell theorem.

Theorem (Hull–Dobell Theorem)

A libnear congruence generator produces a period equal to \(m\), for all seed values, if and only if:

  1. \(m\) and \(c\) are relatively prime,

  2. \(a-1\) is a divisible by all the prime factors of \(m\), and

  3. \(a-1\) is divisible by 4 if \(m\) is divisible by 4.

We will not prove this theorem, but its interesting nonetheless.


4.5.2. Cryptogrophy#

A general overview is available here.

Ciphers#

See this wikipedia article.

RSA Encryption#

See this wikipedia article.