Pseudorandom Number Generators


In this chapter, the author considers existing methods and means of forming pseudo-random sequences of numbers and also are described the main characteristics of random and pseudorandom sequences of numbers. The main theoretical aspects of the construction of pseudo-random number generators are considered. Classification of pseudorandom number generators is presented. The structures and models of the most popular pseudo-random number generators are considered, the main characteristics of generators that affect the quality of the formation of pseudorandom bit sequences are described. The models of the basic mathematical generators of pseudo-random numbers are considered, and also the principles of building hardware generators are presented.
Chapter Preview

Random And Pseudorandom Sequences Of Numbers

Random sequences are widely are used in various fields. They are used in game theory, information security, in the training simulators, in the Monte Carlo methods, which numerical methods are using for the various mathematical tasks solving, and in other fields. Before the advent of computer, the random sequences was being formed by various mathematical and hardware means, invented by man. For example, the coin tossing up or the urn with balls, are using and others. In the future, are compiled a table that contained a large number of random numbers.

Ideal random number sequence is being formed by human using of the various natural events and physical processes. For this purpose, people use the various methods of transformation of the analog values to digital form of number. It is believed that these analogue values are changed by randomly. Each analog value is converted into a number in the discrete intervals of time.

The source of random numbers can be a numerical value of the selected analog value at discrete time moments. For a man important is a successful search for the source of this value, which has a wide range of changes in a given interval of time. Such sources and values include the amount of noise in nonlinear electronic elements (diodes, transistors), ionizing radiation, cosmic radiation, and others.

In fact, this approach uses a conventional transformation of the analog value into its numeric equivalent. For this, researchers are being developed the special converters that consist of a primary the transducer of the physical quantity into an electrical quantity and of the electrical signal transducer into it digital equivalent.

In this approach, a sequence of random numbers а1, а2,…,аi,…, аn is random when any of its next element can not be predicted based on analysis of the previous generated numbers.

The length of the random sequence cannot be bounded, and the range of numbers (range of values) is significantly limited. The width of the range of values depends on the generated numbers from the physical source and from an analog value digitization step.

Furthermore, the ideal random sequence can not be generated by the same source of with a certain time period.

If a random sequence of numbers has been formed by a computer means that implement the established generation algorithm, such a sequence is called a pseudo-random sequence of numbers.

A computing device that implements an algorithm generating pseudorandom numbers, a finite number of states is has. The repeat period of a pseudorandom sequence depends on a set of states, which by the chosen algorithm and by the structure of the computing device are implemented.

The computing device that generates a pseudo-random sequence of numbers, the pseudo-random number generator is called.

Three main properties are used to assess of the generated pseudo-random bit sequence.

  • 1.

    The number of ones and zeros in a sequence of approximately equal and may differ only on 1.

  • 2.

    Identical bit sequences should be distributed so that groups of one element are divided in half in all sequence and groups consisting of two identical elements are divided into four equal parts throughout the sequence, etc.

  • 3.

    When analyzing coincidences with the selected control sequence, the coincidence number must different from the number of non-coincidences on 1 for all binary “1” of a sequence.

These properties are present within the period length of pseudorandom sequence. They characterize the unpredictability of any next element based on the elements sequence previously formed.

It should be remembered that the sequence consisting of all binary “1” may also be formed randomly.


Random And Pseudorandom Number Generators

Random Number Generators generates in nature the random numerical sequences that are not predictable for anyone person (Sanguinetti, Martin, Zbinden, & Gisin, 2014, Tang, Wu, Wu, Deng, Chen, Fan, Zhong, & Xia, 2015). At the same time pseudorandom number generator is regarded as a source of random numbers and as a source of deterministic numbers. The structure of the pseudorandom number generator on Figure 1 is represented.

Complete Chapter List

Search this Book: