User Contributed Dictionary
Adjective
 Of a sequence of numbers, such that it has all the properties of a random sequence following some probability distribution (except true randomness), but is actually generated using a deterministic algorithm.
Extensive Definition
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.
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 entirely
random. 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).
Before modern computing, researchers requiring random numbers would
either generate them through various means (dice, cards,
roulette wheels, etc.)
or use existing random number tables.
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.
John von
Neumann was a pioneer in computerbased 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.
Almost random
 Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. — John von Neumann (1951)
A pseudorandom 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
pseudorandom string will typically be longer than the original
random string, but less random (less entropic,
in the information
theory sense). This can be useful for randomized
algorithms.
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.
Complexitybased 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 nbit string x \in \^n with equal probability of 2^\,. Pseudorandom distributions can be generated deterministically from short random seeds, which are much shorter than the length of the pseudorandom output.A method for distinguishing two distributions
from each other is by taking their statistical
distance. If two distributions p = [p_1, \cdots, p_N] and q =
[q_1, \cdots, q_N] have a very small statistical distance _1 / 2,
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.
Definition
A distribution ensemble \mathrm_n\, is (S(n), \epsilon(n))\, pseudorandom if, for any circuit C of size \leq S(n), with \mathrm_n\, as the uniform random distribution, then

 \left \vert \mathrm_ [C(x) = 1]  \mathrm_ [C(x) = 1] \right \vert \leq \epsilon(n)

\mathrm_n\, is called pseudorandom if it is
pseudorandom for all S(n) = poly(n\,) and \epsilon(n) =
1/O(poly(n))\,. This definition of pseudorandomness is used
primarily in the study of pseudorandom
generators.
Cryptography
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.
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, 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.
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
randomlike numbers very important.
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 π.
See also
External links
 HotBits: Genuine random numbers, generated by radioactive decay
 Random number history
 Using and Creating CryptographicQuality Random Numbers
 In RFC 1750, the use of pseudorandom number sequences in cryptography is discussed at length.
 In Donald E. Knuth, The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd edition), 1997. AddisonWesley Professional, ISBN 0201896842
pseudorandom in Czech: Pseudonáhodná čísla
pseudorandom in German: Pseudozufall
pseudorandom in Spanish: Secuencia
pseudoaleatoria
pseudorandom in French: Pseudoaléatoire
pseudorandom in Ukrainian: Псевдовипадкові
послідовності
pseudorandom in Chinese: 伪随机数