Applications
Contents
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:
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:
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:
\(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.