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.

# From a hash function to a PRNG

Due: February 1
Points: 1

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?