Topic: random number generation

topics > Group: mathematics


kinds of numbers
probabilistic and randomized algorithms
sequence generators


Computers need random numbers for encryption, simulation, randomized algorithms, and identification.

True random numbers are difficult to generate. The basic approach is to build a pool of physically random data, and then manipulate that pool to remove biases and unanticapated correlations.

Pseudorandom numbers are generated. Given the random number seed, you can recreate the sequence. A random salt is a random number added to the input data. It increases the randomness of the input. Linear congruent generators are well understood. Generators may be combined. (cbb 6/06)

Subtopic: unique permanent IDs up

Quote: in a distributed environment need unique, permanent ids (128 bits) for all data [»giffDK7_1985, OK]

Subtopic: true random numbers up

Quote: for true random numbers on heavily used workstations, repeatedly set an alarm and increment until the interrupt occurs. [»lacyJB10_1993]
Quote: how to extract random bits from an unknown, biased source [»mitzM4_2002]
Quote: generate random data from the MD5 hash of an entry pool of timing measurements
Quote: the Ferranti Mark I included a hardware random number generator; e.g., random walk probability [»turiA3_1951]

Subtopic: random sample and permutation generation up

Quote: optimal algorithm for generating random samples and permutations [»bentJ9_1987]

Subtopic: pseduorandom number generation up

Quote: efficient multiply-with-carry random number generators with maximal period; analyzed with b-adic numbers [»goreM10_2003]
Quote: generates pseudorandom functions from a one-way function and a random string; indistinguishable from random functions in polynomial-time [»goldO10_1986]
Quote: squaring mod a Blum-integer is a cryptographically strong pseudorandom bit generator [»goldO10_1986]
Quote: a random number generator should allow multiple streams of random numbers; e.g., the minimal standard [»parkSK7_1993]
Quote: describes a set of software tools for generating multiple sequences of random numbers; needed for simulation [»lecuP3_1991]
Quote: combined Tausworthe random number generators can have a period of 10^18 [»tezuS4_1991]
Quote: ISAAC is a fast pseudorandom number generator with very long cycle lengths, opaque internal state, and no detectable bias [»jenkRJ2_1996]
Quote: software generation of secure, practically strong random numbers; no specialized hardware or privileged system calls [»gutmP1_1998]

Subtopic: problems with random number generators up

Quote: random number generators may be insecure; e.g. using current time and process ID as the seed [»gutmP1_1998]
Quote: a random number generator should never leak its internal state; e.g., input or output data, system swap file, unreviewed code [»gutmP1_1998]
Quote: 30 bit random numbers are repeated too quickly; multiple recursive generators give longer periods and good statistics [»lecuP10_1990]

Subtopic: linear congruent generators up

Quote: 48271 is a better multiplier for the minimal standard Lehmer random number generator [»parkSK7_1993]
Quote: a = 16807 and m = 2^31-1 defines a good random number generator; exhaustively tested and well understood; also 48271 and 69621 [»parkSK10_1988]
Quote: easy to compute the next number in a linear congruential sequence from preceding numbers; so not truly random [»goldO10_1986]
Quote: exhaustive search for optimal multiplicative congruential random number generators with modulus 2^31-1 [»fishGS1_1986]
Quote: implement multiplicative congruential generators with multipliers +- 2^a +- 2^b [»wuPC6_1997]

Subtopic: randoms in a programming language up

Quote: write a random number generator in SL5 as an environment that is resumed for each value [»hansDR5_1978]
QuoteRef: simscrip_1971 ;;169 can specify attribute as producing random numbers

Subtopic: random seed up

Quote: for replicated trials, should reseed with the last random number; otherwise Lehmer generators may fail, especially for small seeds [»parkSK7_1993]
Quote: prompt user for initial seed; for reproducibility, e.g., social security number [»parkSK10_1988]

Subtopic: random salt up

Quote: generate 128-bit salt from arc4random seeded from the kernel's entropy pool of current time and timing data [»provN6_1999]
Quote: UNIX uses encrypted passwords that include a random number assigned by the system to the user [»morrR11_1979, OK]
Quote: a Helix server provides 96-bit capabilities which encrypt access rights to an object with 40 bits padding

Related Topics up

Group: security   (23 topics, 874 quotes)

Topic: encryption (45 items)
Topic: kinds of numbers (24 items)
Topic: randomness (20 items)
Topic: probabilistic and randomized algorithms (11 items)
Topic: sequence generators (16 items)
Topic: simulation (35 items)
Topic: statistics
(12 items)

Updated barberCB 3/06
Copyright © 2002-2008 by C. Bradford Barber. All rights reserved.
Thesa is a trademark of C. Bradford Barber.