Generation methods Random number generation

1 generation methods

1.1 physical methods
1.2 computational methods
1.3 generation probability distribution
1.4 humans

generation methods
physical methods

the earliest methods generating random numbers, such dice, coin flipping , roulette wheels, still used today, in games , gambling tend slow applications in statistics , cryptography.

a physical random number generator can based on random atomic or subatomic physical phenomenon unpredictability can traced laws of quantum mechanics. sources of entropy include radioactive decay, thermal noise, shot noise, avalanche noise in zener diodes, clock drift, timing of actual movements of hard disk read/write head, , radio noise. however, physical phenomena , tools used measure them feature asymmetries , systematic biases make outcomes not uniformly random. randomness extractor, such cryptographic hash function, can used approach uniform distribution of bits non-uniformly random source, though @ lower bit rate.

the appearance of wideband photonic entropy sources such chaotic laser , amplified spontaneous emission noise promote rapid development of physical random number generator. among them, laser chaos gets great concerns produce high-speed physical random numbers due merits of high bandwidth , large amplitude. wang report prototype of high-speed real-time physical random bit generator based on chaotic laser.

various imaginative ways of collecting entropic information have been devised. 1 technique run hash function against frame of video stream unpredictable source. lavarand used technique images of number of lava lamps. hotbits measures radioactive decay geiger–muller tubes, while random.org uses variations in amplitude of atmospheric noise recorded normal radio.

another common entropy source behavior of human users of system. while people not considered randomness generators upon request, generate random behavior quite in context of playing mixed strategy games. security-related computer software requires user make lengthy series of mouse movements or keyboard inputs create sufficient entropy needed generate random keys or initialize pseudorandom number generators.

computational methods

most computer generated random numbers use pseudorandom number generators (prngs) algorithms can automatically create long runs of numbers random properties sequence repeats (or memory usage grows without bound). kind of random numbers fine in many situations not random numbers generated electromagnetic atmospheric noise used source of entropy. series of values generated such algorithms determined fixed number called seed. 1 of common prng linear congruential generator, uses recurrence

x

n
+
1


=
(
a

x

n


+
b
)



mod



m


{\displaystyle x_{n+1}=(ax_{n}+b)\,{\textrm {mod}}\,m}

to generate numbers, a, b , m large integers, ,




x

n
+
1




{\displaystyle x_{n+1}}

next in x series of pseudo-random numbers. maximum number of numbers formula can produce 1 less modulus, m-1. avoid non-random properties of single linear congruential generator, several such random number generators different values of multiplier coefficient, a, can used in parallel, master random number generator selects among several different generators.

a simple pen-and-paper method generating random numbers so-called middle square method suggested john von neumann. while simple implement, output of poor quality. has short period , severe weaknesses, such output sequence converging zero. recent innovation combine middle square weyl sequence. method produces high quality output through long period. see middle square weyl sequence prng.

most computer programming languages include functions or library routines provide random number generators. designed provide random byte or word, or floating point number uniformly distributed between 0 , 1.

the quality i.e. randomness of such library functions varies predictable output, cryptographically secure. default random number generator in many languages, including python, ruby, r, idl , php based on mersenne twister algorithm , not sufficient cryptography purposes, explicitly stated in language documentation. such library functions have poor statistical properties , repeat patterns after tens of thousands of trials. initialized using computer s real time clock seed, since such clock measures in milliseconds, far beyond person s precision. these functions may provide enough randomness tasks (for example video games) unsuitable high-quality randomness required, such in cryptography applications, statistics or numerical analysis.

much higher quality random number sources available on operating systems; example /dev/random on various bsd flavors, linux, mac os x, irix, , solaris, or cryptgenrandom microsoft windows. programming languages, including mentioned above, provide means access these higher quality sources.

generation probability distribution

there couple of methods generate random number based on probability density function. these methods involve transforming uniform random number in way. because of this, these methods work equally in generating both pseudo-random , true random numbers. 1 method, called inversion method, involves integrating area greater or equal random number (which should generated between 0 , 1 proper distributions). second method, called acceptance-rejection method, involves choosing x , y value , testing whether function of x greater y value. if is, x value accepted. otherwise, x value rejected , algorithm tries again.

by humans

random number generation may performed humans, in form of collecting various inputs end users , using them randomization source. however, studies find human subjects have degree of non-randomness when attempting produce random sequence of e.g. digits or letters. may alternate between choices when compared random generator; thus, approach not used.