Random number generation

 

Random number generation

From Wikipedia, the free encyclopedia
Dice are an example of a mechanical hardware random number generator. When a cubical die is rolled, a random number from 1 to 6 is obtained.

Random number generation is a process by which, often by means of a random number generator (RNG), a sequence of numbers or symbols that cannot be reasonably predicted better than by random chance is generated. This means that the particular outcome sequence will contain some patterns detectable in hindsight but unpredictable to foresight. True random number generators can be hardware random-number generators (HRNGS) that generate random numbers, wherein each generation is a function of the current value of a physical environment's attribute that is constantly changing in a manner that is practically impossible to model. This would be in contrast to so-called "random number generations" done by pseudorandom number generators (PRNGs) that generate numbers that only look random but are in fact pre-determined—these generations can be reproduced simply by knowing the state of the PRNG.

Various applications of randomness have led to the development of several different methods for generating random data. Some of these have existed since ancient times, among whose ranks are well-known "classic" examples, including the rolling of dice, coin flipping, the shuffling of playing cards, the use of yarrow stalks (for divination) in the I Ching, as well as countless other techniques. Because of the mechanical nature of these techniques, generating large quantities of sufficiently random numbers (important in statistics) required much work and time. Thus, results would sometimes be collected and distributed as random number tables.

Several computational methods for pseudorandom number generation exist. All fall short of the goal of true randomness, although they may meet, with varying success, some of the statistical tests for randomness intended to measure how unpredictable their results are (that is, to what degree their patterns are discernible). This generally makes them unusable for applications such as cryptography. However, carefully designed cryptographically secure pseudorandom number generators (CSPRNGS) also exist, with special features specifically designed for use in cryptography.

Practical applications and uses[edit]

Main article: Applications of randomness

Random number generators have applications in gambling, statistical sampling, computer simulation, cryptography, completely randomized design, and other areas where producing an unpredictable result is desirable. Generally, in applications having unpredictability as the paramount feature, such as in security applications, hardware generators are generally preferred over pseudorandom algorithms, where feasible.

Pseudorandom number generators are very useful in developing Monte Carlo-method simulations, as debugging is facilitated by the ability to run the same sequence of random numbers again by starting from the same random seed. They are also used in cryptography – so long as the seed is secret. Sender and receiver can generate the same set of numbers automatically to use as keys.

The generation of pseudorandom numbers is an important and common task in computer programming. While cryptography and certain numerical algorithms require a very high degree of apparent randomness, many other operations only need a modest amount of unpredictability. Some simple examples might be presenting a user with a "random quote of the day", or determining which way a computer-controlled adversary might move in a computer game. Weaker forms of randomness are used in hash algorithms and in creating amortized searching and sorting algorithms.

Some applications which appear at first sight to be suitable for randomization are in fact not quite so simple. For instance, a system that "randomly" selects music tracks for a background music system must only appear random, and may even have ways to control the selection of music: a true random system would have no restriction on the same item appearing two or three times in succession.

"True" vs. pseudo-random numbers[edit]

Main articles: Pseudorandom number generator and Hardware random number generator
See also: Cryptographically secure pseudorandom number generator

There are two principal methods used to generate random numbers. The first method measures some physical phenomenon that is expected to be random and then compensates for possible biases in the measurement process. Example sources include measuring atmospheric noise, thermal noise, and other external electromagnetic and quantum phenomena. For example, cosmic background radiation or radioactive decay as measured over short timescales represent sources of natural entropy.

The speed at which entropy can be obtained from natural sources is dependent on the underlying physical phenomena being measured. Thus, sources of naturally occurring "true" entropy are said to be blocking – they are rate-limited until enough entropy is harvested to meet the demand. On some Unix-like systems, including most Linux distributions, the pseudo device file /dev/random will block until sufficient entropy is harvested from the environment.[1] Due to this blocking behavior, large bulk reads from /dev/random, such as filling a hard disk drive with random bits, can often be slow on systems that use this type of entropy source.

The second method uses computational algorithms that can produce long sequences of apparently random results, which are in fact completely determined by a shorter initial value, known as a seed value or key. As a result, the entire seemingly random sequence can be reproduced if the seed value is known. This type of random number generator is often called a pseudorandom number generator. This type of generator typically does not rely on sources of naturally occurring entropy, though it may be periodically seeded by natural sources. This generator type is non-blocking, so they are not rate-limited by an external event, making large bulk reads a possibility.

Some systems take a hybrid approach, providing randomness harvested from natural sources when available, and falling back to periodically re-seeded software-based cryptographically secure pseudorandom number generators (CSPRNGs). The fallback occurs when the desired read rate of randomness exceeds the ability of the natural harvesting approach to keep up with the demand. This approach avoids the rate-limited blocking behavior of random number generators based on slower and purely environmental methods.

While a pseudorandom number generator based solely on deterministic logic can never be regarded as a "true" random number source in the purest sense of the word, in practice they are generally sufficient even for demanding security-critical applications. Carefully designed and implemented pseudorandom number generators can be certified for security-critical cryptographic purposes, as is the case with the yarrow algorithm and fortuna. The former is the basis of the /dev/random source of entropy on FreeBSD, AIX, OS X, NetBSD, and others. OpenBSD uses a pseudorandom number algorithm known as arc4random.[2]

Comments

Post a Comment

Popular posts from this blog

Generation methods

Image
  Generation methods [ edit ] Physical methods [ edit ] Main article:  Hardware random number generator The earliest methods for generating random numbers, such as dice, coin flipping and roulette wheels, are still used today, mainly in games and gambling as they tend to be too slow for most applications in statistics and cryptography. A physical random number generator can be based on an essentially random atomic or subatomic physical phenomenon whose unpredictability can be traced to the laws of  quantum mechanics . Sources of  entropy  include  radioactive decay ,  thermal noise ,  shot noise , avalanche noise in  Zener diodes ,  clock drift , the timing of actual movements of a  hard disk  read-write head, and  radio noise . However, physical phenomena and tools used to measure them generally feature asymmetries and  systematic biases  that make their outcomes not uniformly random. A  randomness extracto...
Read more

F-TEST

Image
  F -test An  F -test  is any  statistical test  in which the  test statistic  has an  F -distribution  under the  null hypothesis . It is most often used when  comparing statistical models  that have been fitted to a  data  set, in order to identify the model that best fits the  population  from which the data were sampled. Exact " F -tests" mainly arise when the models have been fitted to the data using  least squares . The name was coined by  George W. Snedecor , in honour of  Ronald Fisher . Fisher initially developed the statistic as the variance ratio in the 1920s. [1] Common examples [ edit ] Common examples of the use of  F -tests include the study of the following cases: The hypothesis that the  means  of a given set of  normally distributed  populations, all having the same  standard deviation , are equal. This is perhaps the best-known  F -test, an...
Read more

NORMED VECTOR SPACES AND INNER PRODUCT SPACES

Image
Normed vector spaces and inner product spaces [ edit ] Main articles:  Normed vector space  and  Inner product space "Measuring" vectors is done by specifying a  norm , a datum which measures lengths of vectors, or by an  inner product , which measures angles between vectors. Norms and inner products are denoted  | � |  and  ⟨ � , � ⟩ ,  respectively. The datum of an inner product entails that lengths of vectors can be defined too, by defining the associated norm  | � | := ⟨ � , � ⟩ .  Vector spaces endowed with such data are known as  normed vector spaces  and  inner product spaces , respectively. [39] Coordinate space  � �  can be equipped with the standard  dot product : ⟨ � , � ⟩ = � ⋅ � = � 1 � 1 + ⋯ + � � � � . In  � 2 ,  this reflects the common notion of the angle between two vectors  �  and  � ,  by the  law of cosines : � ⋅ � = cos ⁡ ( ∠ ( � , � ) ) ⋅ | � | ⋅...
Read more