This article may require cleanup to meet Wikipedia's quality standards. Please discuss this issue on the talk page or replace this tag with a more specific message. This article has been tagged since May 2007.

A pseudorandom process is a process that appears random but is not. Pseudorandom sequences typically exhibit statistical randomness while being generated by an entirely deterministic causal process. Such a process is easier to produce than a genuine random one, and has the benefit that it can be used again and again to produce exactly the same numbers, useful for testing and fixing software. Image File history File links Broom_icon. ... The word random is used to express lack of order, purpose, cause, or predictability in non-scientific parlance. ... A numeric sequence is said to be statistically random when it contains no recognizable patterns or regularities; sequences such as the results of an ideal die roll, or the digits of Pi (as far as we can tell) exhibit statistical randomness. ...

To date there is no known method to produce true randomness, because due to the very nature of randomness, any factor determining the outcome would mean that it is not random at all. The random number generation functions provided in all software packages are therefore pseudorandom.

History

The generation of random numbers has many uses (mostly in statistics, for random sampling, and simulation); originally researchers needing random numbers would generate them through various means - dice, cards, roulette wheels ... or use existing random number tables. This article is about the field of statistics. ... Sampling is that part of statistical practice concerned with the selection of individual observations intended to yield some knowledge about a population of concern, especially for the purposes of statistical inference. ... This article is about the general term. ... Dice (the plural of die, from Old French de, from Latin datum something given or played [1]) are small polyhedral objects, usually cubical, used for generating random numbers or other symbols. ... Some typical modern playing cards. ... Roulette is a casino and gambling game named after the French word meaning small wheel. In the game a croupier spins a wheel in one direction, then spins a ball in the opposite direction around a tilted circular surface running around the circumference of the wheel. ...

The first attempt to provide researchers with a ready supply of random digits was in 1927, when the Cambridge University Press published a table of 41,600 digits developed by Leonard H.C. Tippet. In 1947, the RAND Corporation generated numbers by the electronic simulation of a roulette wheel; the results were eventually published in 1955 as A Million Random Digits with 100,000 Normal Deviates. The RAND Corporation is a nonprofit global policy think tank first formed to offer research and analysis to the United States armed forces. ... An important 20th century work in the field of statistics and random numbers was the RAND Corporations book of tables containing, and entitled, A Million Random Digits with 100,000 Normal Deviates. ...

John von Neumann was a pioneer in computer-based random number generators. In 1951, Derrick Henry Lehmer invented the linear congruential generator, used in most pseudorandom number generators today. With the spread of the use of computers, algorithmic pseudorandom number generators replaced random number tables, and "true" random number generators (Hardware random number generators) are only used in a few cases. For other persons named John Neumann, see John Neumann (disambiguation). ... Year 1951 (MCMLI) was a common year starting on Monday (link will display the full calendar) of the Gregorian calendar. ... Derrick Henry Lehmer (February 23, 1905–May 22, 1991) was an American mathematician who refined Edouard Lucas work in the 1930s and devised the Lucas-Lehmer test for Mersenne primes. ... Linear congruential generators (LCGs) represent one of the oldest and best-known pseudorandom number generator algorithms. ... A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ... In computing, a hardware random number generator is an apparatus that generates random numbers from a physical process. ...

Almost random

Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. — John von Neumann (1951)

A pseudo-random variable is a variable which is created by a deterministic procedure (often a computer program or subroutine) which (generally) takes random bits as input. The pseudo-random string will typically be longer than the original random string, but less random (less entropy, in the information theory sense). This can be useful for randomized algorithms. For other persons named John Neumann, see John Neumann (disambiguation). ... Year 1951 (MCMLI) was a common year starting on Monday (link will display the full calendar) of the Gregorian calendar. ... Claude Shannon In information theory, the Shannon entropy or information entropy is a measure of the uncertainty associated with a random variable. ... Not to be confused with information technology, information science, or informatics. ...

Pseudorandom number generators are widely used in such applications as computer modeling (e.g., Markov chains), statistics, experimental design, etc. Some of them are sufficiently random to be useful in these applications. Many are not, and considerable sophistication is required to correctly determine the difference for any particular purpose. Incautious use of readily available random number generators has caused considerable, and long sustained, damage to the worth of large numbers of research projects for many years. The RANDU generator routine available on many large mainframe computers for decades had considerable, widely unappreciated, faults. A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ... In mathematics, a Markov chain, named after Andrey Markov, is a discrete-time stochastic process with the Markov property. ... RANDU is an infamous linear congruential pseudorandom number generator which has been used since the 1960s. ... For other uses, see Mainframe. ...

Complexity-based pseudorandomness

A distribution is considered to be pseudorandom if it cannot be distinguished from the truly (Uniform) random distribution by any efficient (polynomial time) procedure or circuit. The uniform distribution, for a length parameter n assigns each n-bit string with equal probability of . Pseudorandom distributions can be generated deterministically from short random seeds, which are much shorter than the length of the pseudorandom output. In mathematics and statistics, a probability distribution is a function of the probabilities of a mutually exclusive and exhaustive set of events. ... The term deterministic may refer to: the more general notion of determinism from philosophy, see determinism a type of algorithm as discussed in computer science, see deterministic algorithm scientific determinism as used by Karl Popper and Stephen Hawking deterministic system in mathematics deterministic system in philosophy deterministic finite state machine... This writeup is about biological seeds; for other meanings see Seed (disambiguation). ...

A method for distinguishing two distributions from each other is by taking their statistical distance. If two distributions and have a very small statistical distance , there exists no circuit, S, such that S can distinguish them well, even with no restriction on the size of S. Also, if the size of S is too small then it may not be able to distinguish some distributions that are very different. In mathematics, the total variation of a real-valued function f on the bounded interval [a, b] is the supremum running over all partitions P = { x1, ..., xn } of the interval [a, b]. In effect, the total variation is the vertical component of the arc-length of the graph of f. ...

Definition

A distribution ensemble is pseudorandom if, for any circuit C of size , with as the uniform random distribution, then

is called pseudorandom if it is pseudorandom for all and . This definition of pseudorandomness is used primarily in the study of pseudorandom generators. Let G be a deterministic polynomial time function from N<? to N<? with stretch function l:N ? N, so that if x has length n then G(x) has length l(n). ...

Cryptography

See also: Cryptographically secure pseudorandom number generator

For such applications as cryptography, the use of pseudorandom number generators (whether hardware or software or some combination) is insecure. When random values are required in cryptography, the goal is to make a message as hard to crack as possible, by eliminating or obscuring the parameters used to encrypt the message (the key) from the message itself or from the context in which it is carried. Pseudorandom sequences are deterministic and reproducible; all that is required to discover and reproduce a pseudorandom sequence is the algorithm used to generate it and the initial seed. So the entire sequence of numbers is only as powerful as the randomly chosen parts - sometimes the algorithm and the seed, but usually only the seed. A cryptographically secure pseudo-random number generator (CSPRNG) is a pseudo-random number generator (PRNG) with properties that make it suitable for use in cryptography. ... The German Lorenz cipher machine, used in World War II for encryption of very high-level general staff messages Cryptography (or cryptology; derived from Greek κρυπτός kryptós hidden, and the verb γράφω gráfo write or λεγειν legein to speak) is the study of message secrecy. ... A key is a piece of information that controls the operation of a cryptography algorithm. ...

There are many examples in cryptographic history of cyphers, otherwise excellent, in which random choices were not random enough and security was lost in direct consequence. The World War II Japanese PURPLE cypher machine used for diplomatic communications is a good example. It was consistently broken throughout WWII, and indeed from somewhat before the United States entered that war, mostly because the "key values" used were insufficiently random. They had patterns, and those patterns made any intercepted traffic readily decryptable. Had keys (ie, the initial settings of the stepping switches in the machine) been made unpredictably (ie, randomly), that traffic would have been much harder to break, and perhaps even secure in practice.^{[citation needed]} Combatants Allied powers: China France Great Britain Soviet Union United States and others Axis powers: Germany Italy Japan and others Commanders Chiang Kai-shek Charles de Gaulle Winston Churchill Joseph Stalin Franklin Roosevelt Adolf Hitler Benito Mussolini Hideki Tōjō Casualties Military dead: 17,000,000 Civilian dead: 33,000... This article is about the color. ...

Users and designers of cryptography are strongly cautioned to treat their randomness needs with the utmost care. Absolutely nothing has changed with the era of computerized cryptography, except that patterns in pseudorandom data are easier to discover than ever before. Randomness is, if anything, more important than ever.

Monte Carlo method simulations

Computers are used to simulate everything from nuclear reactions to the economy. These are examples of Monte Carlo method Simulations. A Monte Carlo method Simulation is defined as any method that utilizes sequences of random numbers to perform the simulation. Other simulations include quantum chromo dynamics, radiation cancer therapy, traffic flow, stellar evolution and VLSI design. All these simulations require the use of random numbers and therefore pseudorandom number generators, which makes creating random like generators very important. Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations. ... A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ...

An easy example of how a computer would do a Monte Carlo method Simulation is the calculation of π. If a square enclosed a circle and a point were randomly chosen inside the square the point would either lie inside the circle or outside it. If the process were repeated many times, you can see that the ratio of the random points that lie inside the circle to outside it is proportional to ratio of the circle area to the square area. From this we can estimate π. When a circles diameter is 1, its circumference is Ï€. Pi or Ï€ is the ratio of a circles circumference to its diameter in Euclidean geometry, approximately 3. ...

See also

• Disperser
• Expander graph
• Extractor
• Random variable
• PN Sequences
• Pseudo-random binary sequence
• Pseudorandom number generator
• List of random number generators

An (N, M, D, K, e)-disperser is a bipartite graph with N nodes on the left side, each with degree D, and M nodes on the right side, such that every subset of K nodes on the left side is connected to more than (1 &#8722; e) fraction of... In combinatorics, an expander graph refers to a sparse graph which has high connectivity properties, quantified using vertex or edge expansion as described below. ... Mathematics An (N,M,D,K,e)-extractor is a bipartite graph with N nodes on the left and M nodes on the right such that each node on the left has D neighbors (on the right), which has the added property that for any subset A of N of... In probability theory, a random variable is a quantity whose values are random and to which a probability distribution is assigned. ... // PN SEQUENCES --Rdschwarz 15:28, 20 August 2005 (UTC) Spread Spectrum technology is being applied to many areas of modern communications such as Wireless Lans, Cellular Telephones, Global Positioning System (GPS), and Very Small Aperture Satellite Terminals (VSAT) just to name a few. ... A binary sequence (BS) is a sequence of N aj bits (j=0,1,...,N-1), i. ... A pseudorandom number generator (PRNG) is an algorithm to generate a sequence of numbers that approximate the properties of random numbers. ... Computer random number generators are important in mathematics, cryptography and gambling. ...

External links

• Random number history
• Using and Creating Cryptographic-Quality Random Numbers
• In RFC 1750, the use of pseudo-random number sequences in cryptography is discussed at length.
• In Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition), 1997. Addison-Wesley Professional, ISBN 0-201-89684-2