8. Pseudo-random numbers L. Blum, M. Blum, and M. Shub designed a more effi-

cient pseudo-random number generator with the additional property that the *i*th bit

*b_i* can be computed "directly" from *i* and the seed *x₀*. Use Miller-Rabin(*n*,*s*) to implement it as follows.

(a) Generate two large prime numbers, *p* and *q*, such that *p* = 3 mod 4 and *q* =

3 mod 4. (Which is more efficient to perform first: the test of whether *p* is prime, or the test of whether *p* and *q* both equal 3 mod 4?)

(b) Compute n = p ⋅ q; such an n, with p and q as in (a), is called a Blum integer.

(c) Choose a random integer x ∈ Z such that x has no common factor with n; note that this choice also depends on a pseudo-random generator – say, the one that Miller-Rabin(n,s) uses.

(d) Compute the seed x₀ = x² mod n for the pseudo-random number generator to be constructed.

(e) The ith bit b_i of the new pseudo-random output sequence is the least significant bit of x_i, where x_i = x²_i-1 mod n for all i ∈ N.

(f) Assume that x_i = x₀^{2imod(p-1)-(q-1)} mod n (2.14)
(2.15)
for all i ∈ N. (The mathematics required for showing this will be addressed in Exercise 2.11-12, p. 42.) The user of your algorithm should be able to choose whether the sequence is generated based on definition (2.14) or (2.15). Compare the efficiency of these versions.
Not only is this generator useful – since it allows us to compute the ith bit without having computed the previous bits of the sequence – it also has the pleasant property that the generated sequence is unpredictable to the left and right: one cannot predict the bit to the left (or right) of a given bit in the sequence.