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{array}{r} x_{n + 1} = a x_{n} + c mod m \end{array}

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, \dots)

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, \dots, 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:

$m$ and $c$ are relatively prime,
$a - 1$ is a divisible by all the prime factors of $m$ , and
$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#