Problem 27

This is the archived version of this course from the Spring 2013 semester. You might find something more recent by visitning my teaching page.

Recall from data structures class that a *hash function* \(h(x)\) takes some input integer \(0 \le x \lt m\) and produces an output in the range \(0 \le h(x) \lt n\), for some integers *m* and *n* (usually *m* is much larger than *n*).

A hash function is definitely not random: if you give it the same input, it must always produce the same output. But a good hash function is said to "appear random" in that there is no discernible relationship between the input and the output.

Describe how a hash function \(h(x)\) as defined above could be used to create a PRNG. What would the parameters of the PRNG be? Do you think this would be a good way to generate pseudo-random numbers?