# Random Number Generators: True Randomness

By Haadi

I Introduction:

Random (adj): a: lacking a definite plan,Random Number Generators: True Randomness Articles purpose, or pattern. b: made, done, or chosen at random c: relating to, having, or being elements or events with definite probability of occurrence. d: being or relating to a set or to an element of a set each of whose elements has equal probability of occurrence. [Oxford English Dictionary]

Before commencing deep discussion of the art of “true randomality”, it must first be made clear that true randomness is theoretically impossible by the defining principals of our universe. The definition above clearly defines the paradox that surrounds the concept of randomality when subject to probability. In essence we will claim that “truly random” is the state in which for a given set A, for any i, element in A, i if chosen at random, has a probability of [1/|A|] (where |x| denotes cardinality of the set) of occurrence. This is how we judge the “randomness” of a Random Number Generator (RNG(s)), by its ability to exploit probability; given a set A, a perfect RNG will not repeat an element before the set is exhausted; described as the period of a generator, its point of repetition.

I.i Various Uses of Random Number Generators:

Random numbers have a multitude of applications. Of particular interest to this study and intended future studies by the author is Cryptography. Many cryptographic protocols make use of RNGs, particularly, public key cryptography (RSA) and some implementations of symmetric ciphers (DES, Serpent). Besides cryptographic function however, RNGs are used in Simulations, for the realistic recreation of “natural” occurrences; in this case, computer games are qualified as simulations, in which RNGs are heavily used in conjunction with probability weights (Gaussian). They’re also used for integrity testing on various computer applications during development, even hardware tests, such as GPU to memory pipelines on AGP based graphic cards. Among those mentioned are many other uses and purposes for the development and “perfection” of making truly random choices.

I.ii Brief Algorithm Introduction:

Random number generating algorithms come in multiple flavors; these can be separated into two main groups, linear number generators (LNG(s)) and non-linear number generators (NLNG(s)). Each group contains multiple types of RNGs and each of these, have their purpose and uses. It is important to know that although not all generators are made equal, good generators have purposes for which other good generators are not suited to perform.

II Linear Congruential Generators:

LNGs ultimately generate a sequence of integers between 0 and a given modulus, for the equation Ij+1 = aIj + c (mod m). In this equation, m is used as the modulus, a is a multiplier, and c is an increment. The sequence will repeats within a period of m, where m is usually prime.

The advantage of the LNG is immediately noticed by the equation above; its fast, requiring one multiplication, one addition, and one modulus. This immediately lends itself to explaining its wide uses. This type of generator is used in a multitude of applications for which the nature of the random sequence doesn’t matter, only that it be a different sequence from execution to execution; Monte Carlo simulations for example. The speed and simplicity of the algorithm has also led to the amount of flavors developed for different applications. For instance, the equation above is the same equation that the ANSI C/C++ committee has dubbed for use with these languages, given appropriate values for a, c, and m. Besides the linear equation, there are also:

Quadratic LCG:
Xn = (aXn-12 + bXn-1 + c) mod m

Cubic LCG:
Xn = (aXn-13 + bXn-12 + cXn-1 + d) mod m

It is possible to force an LCG to be probabilistically correct, by creating uniform deviations. The problem with focusing on the deviation of an LCG is that a well deviated LCG will have an extended period, but its complexity increases, due to the deviation, sometimes beyond the useful range of LCGs. It is also possible to use deviations normalized in a given interval, such as Gaussian deviations, where the period is lengthened such that every integer in the given field is selected.

III Inversive Congruential Generators and Linear Feedback Shift Registers:

Defined as our non-linear generators, ICGs and EICGs, developed by Eichenauer and Lehn (1986, 1993) are defined by the following congruence:

yn+1 = ayn + b (mod m)

Where, for practicality, m is also chosen as a prime number in parallel to LCGs. These two generators are most notable due to their speed and period efficiency compromise. They produce relatively long periods, in (5 – 10x average) more time, than LCG.

III.i Linear Feedback Shift Registers:

LFSR generators are of more relevance here, as a suitable alternative to LCGs for cryptographic applications. Shift registers work on the concept of generating on the bit level, instead of in a base 10 finite field. They address the problem of creating uniform distribution of single random bits, with 0 and 1 equally probable.

LFSR generators are made up of two parts, the shift register and the feedback function. The shift register is the bit sequence, in which the size of the shift register is determined by the length of its bits. When bits are needed, the register is shifted 1 bit to the right, and the left bit is computed based on the remaining bits in the register. The simplest method of representing LFSRs feedback function is the XOR of key register bits. The method used by the feedback function is called tap sequence.

It’s obvious, that an n-bit LFSR can be in 2n -1 states; noting that the size of the register denotes its length. Therefore, a 4 bit register (1111 would be called a 4 bit register, based on the cardinality of the register, rather than the value of the high order bit, base 10) would yield 24-1, or 15 unique states. With an output sequence of the least significant bits following the shifts, the size of the register defines a period or 2n – 1 bits before repetition, therefore yielding a base 10 value of 22**n -1 as maximum value, and period. In order to reach this maximum period, a primitive polynomial must be formed by the tap sequence, where the degree of the polynomial yields the length of the shift register.