15-583: Algorithms in the Real World

15-583: Algorithms in the Real World

Generating Random and Pseudorandom Numbers Some slides from CS 15-853:Algorithms in the Real World, Carnegie Mellon University Page1 Random Numbers in the Real World https://fitforrandomness.files.wordpress.com/2010/11/dilbert-does-randomness. jpg https://xkcd.com/221/

Page2 Random number sequence definitions Each element is chosen independently from a probability distribution [Knuth]. Randomness of a sequence is the Kolmogorov complexity of the sequence (size of smallest Turing machine that generates the sequence) infinite sequence should require infinite size Turing machine. Page3 Environmental Sources of

Randomness Radioactive decay http://www.fourmilab.ch/hotbits/ Radio frequency noise http://www.random.org Noise generated by a resistor or diode. Canada http://www.tundra.com/ (find the data encryption section, then look under RBG1210. My device is an NM810 which is 2?8? RBG1210s on a PC card) Colorado http://www.comscire.com/ Holland http://valley.interact.nl/av/com/orion/home.html Sweden http://www.protego.se Inter-keyboard timings (watch out for buffering) Inter-interrupt timings (for some interrupts) Page4 Combining Sources of

Randomness Suppose r1, r2, , rk are random numbers from different sources. E.g., r1 = from JPEG file r2 = sample of hip-hop music on radio r3 = clock on computer b = r1 r2 rk If any one of r1, r2, , rk is truly random, then so is b. Page5

Skew Correction Von Neumanns algorithm converts biased random bits to unbiased random bits: Collect two random bits. Discard if they are identical. Otherwise, use first bit. Efficiency? Page6 Chi Square Test Experiment with k outcomes, performed n times. p1, , pk denote probability of each outcome Y1, , Yk denote number of times each outcome occured Large X2 indicates deviance from random chance

Page7 Analysis of random.org numbers John Walkers Ent program Entropy = 7.999805 bits per character. Optimum compression would reduce the size of this 1048576 character file by 0 percent. Chi square distribution for 1048576 samples is 283.61, and randomly would exceed this value 25.00 percent of the times. Arithmetic mean value of data bytes is 127.46 (127.5 = random). Monte Carlo value for PI is 3.138961792 (error 0.08 percent). Serial correlation coefficient is 0.000417

(totally uncorrelated = 0.0 Page8 Analysis of JPEG file Entropy = 7.980627 bits per character. Optimum compression would reduce the size of this 51768 character file by 0 percent. Chi square distribution for 51768 samples is 1542.26, and randomly would exceed this value 0.01 percent of the times. Arithmetic mean value of data bytes is 125.93 (127.5 = random). Monte Carlo value for Pi is 3.169834647 (error 0.90 percent). Serial correlation coefficient is 0.004249 (totally uncorrelated = 0.0).

Page9 Pseudorandom Number Generators A pseudorandom number generator (PRNG) is an algorithm for generating a sequence of numbers whose properties approximate the properties of sequences of random numbers. The PRNG-generated sequence is not truly random, because it is completely determined by an initial value, called the PRNG's seed (which may include truly random values). Although sequences that are closer to truly random can be generated using hardware

random number generators, pseudorandom number generators are important in practice for their speed and reproducibility. Page10 Pseudorandom Number Generators PRNGs are central in applications such as simulations (e.g. for the Monte Carlo method), electronic games (e.g. for procedural generation), and cryptography. Cryptographic applications require the output not to be predictable from earlier outputs. Anyone who considers arithmetical methods of

producing random digits is, of course, in a state of sin. - John Von Neumann, 1951 Page11 Simple Visual Test Create a visualization of the consecutive tuples of numbers it produces. Humans are really good at spotting patterns. Page12 Linear Congruential Generator (LCG)

x0 = given, x x 0 x1 x2 x3 x4 n+1 = P1 xn + P2 (mod N) =79, N = 100, P

= = = = 79*263 48*263 95*263 56*263 + + + + 71

71 71 71 1 = 263, and P (mod (mod (mod (mod 100) 100) 100)

100) = = = = 2 n = 0,1,2,... (*) = 71 20848

12695 25056 14799 (mod (mod (mod (mod 100) 100) 100) 100) = =

= = 48, 95, 56, 99, Sequence: 79, 48, 95, 56, 99, 8, 75, 96, 68, 36, 39, 28, 35, 76, 59, 88, 15, 16, 79, 48, 95 Park and Miller: P1 = 16807, P2 = 0, N= 231-1 = 2147483647, x0 = 1. ANSI C rand(): P1 = 1103515245, P2 = 12345, N = 231, x0 = 12345 Page13

Example Comparison Page14 Plot (xi, xi+1) Page15 Plot (xi, xi+1) Park and Miller Page16 (xi, xi+1), (xi,xi+2), (xi, xi+2) http://www.math.utah.edu/~alfeld/Random/Random.html

Page17 Visual Test in 3D Three-dimensional plot of 100,000 values generated with IBM RANDU routine. Each point represents 3 consecutive pseudorandom values. It is clearly seen that the points fall in 15 twodimensional planes. Page18 Matsumotos Marsenne Twister Considered one of the best linear congruential generators. http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/emt.html

Page19 Example Visual Test Page20 Cryptographically Strong Pseudorandom Number Generator Next-bit test: Given a sequence of bits x1, x2, , xk, there is no polynomial time algorithm to generate xk+1. Yao [1982]: A sequence that passes the next-bit test passes all other polynomial-time statistical tests for randomness. Page21

Hash/Encryption Chains key Hash or Encryption Function xi+1 Last bit of xi+1 xi (need a random seed x0 or key value) Page22

Some Encryption and Hash Functions SHA-1 Hash function https://en.wikipedia.org/wiki/SHA-1 MD5 Hash function https://en.wikipedia.org/wiki/MD5 Data Encryption Standard (DES) https://en.wikipedia.org/wiki/Data_Encryption_Standard Advanced Encryption Standard (AES) https://en.wikipedia.org/wiki/Advanced_Encryption_Standard Page23 BBS secure random bits BBS (Blum, Blum and Shub, 1984) Based on difficulty of factoring, or finding

square roots modulo n = pq. Fixed p and q are primes such that p = q = 3 (mod 4) n = pq (is called a Blum integer) For a particular bit seq. Seed: random x relatively prime to n. Initial state: x0 = x2 ith state: xi = (xi-1)2 i ith bit: lsb of xi

2 mod ( n ) Note that: x 0 xi (mod n) Therefore knowing p and q allows us to find x0 from xi Page24

Recently Viewed Presentations

  • 6 Traits of writing - Moore Public Schools

    6 Traits of writing - Moore Public Schools

    6 traits of writing . Ideas. Organization. Word Choice. Voice. Sentence Fluency. Conventions . Scored 1-5, 5 is the highest score, 1 is the lowest.
  • Inventory Management - University of Texas at Austin

    Inventory Management - University of Texas at Austin

    Conduct an ABC analysis of inventory items. ... Learning Objectives Role of Inventory in Services Considerations in Inventory Systems Relevant Inventory Costs Inventory Management Questions Inventory Models Inventory Levels For EOQ Model Annual Costs For EOQ Model EOQ Formula Annual...
  • The Psychology of Survey Responses: Implications for ...

    The Psychology of Survey Responses: Implications for ...

    Roger Tourangeau, SRC, JPSM Robert M. Groves, SRC, JPSM Stanley Presser, JPSM ... George W. Bush ran on the Republican ticket against John Kerry for the Democrats. In the 2004 presidential election, did things come up that kept you from...
  • BASIC COUNTING - Mathematics

    BASIC COUNTING - Mathematics

    1/26/2004 Discrete Mathematics for Teachers, UT Math 504, Lecture 03 Sets, Boolean Algebras, and Relations Sections 2.1-2.5 Introduction to Sets History and Philosophy Informally a set is a collection of objects. ... represented by curves with arrows. That is, a...
  • Hess's Law

    Hess's Law

    Tips for applying Hess's Law… Look at the final equation that you are . trying to create first… Find a molecule from that eq. that is only in one of the given equations (i.e. CH. 3 OH, CO 2). Make...
  • Modern Chemistry Chapter 7 Chemical Formulas & Chemical Compounds

    Modern Chemistry Chapter 7 Chemical Formulas & Chemical Compounds

    Modern Chemistry Chapter 7 Chemical Formulas & Chemical Compounds A chemical formula indicates the kind and relative number of atoms in a chemical compound. C8H18 (octane) has 8 carbon and 18 hydrogen atoms.
  • Georgia Credit Union Affiliates Annual Meeting May 8, 2004

    Georgia Credit Union Affiliates Annual Meeting May 8, 2004

    Inflation will fall below the Federal Reserve's inflation target of 2% in 2013. Core inflation (excluding food and energy prices) will also fall below 2% in 2013 due to a weak economy and falling commodity prices. Low core inflation will...
  • Franklin River - Outdoor School

    Franklin River - Outdoor School

    Franklin River Martin Eriksson Lake Peddder Lake Pedder was an issue between the Hydro Electric Scheme (HEC) and environmentalists. The HEC had the full support of the Tasmanian State Government The two environmentalist groups (South West Committee and Lake Pedder...