The Blum-Blum-Shub generator produces pseudorandom bits as follows. We set a large natural M, set a...

  

Transcribed Image Text:

The Blum-Blum-Shub generator produces pseudorandom bits as follows. We set a large natural M, set a natural seed ro, and define ₁+1 for each i as r(modM). We let each pseudorandom bit bi be the lowest-order bit of x,. Most of the motivation for this generator is beyond us at this point, but we can explore the choice of M, borrowing some work from Chapter 3. (a) Show that at least some primes of the form 4n+1 (for example, try starting with 17) are bad choices for M. (b) Show that if M is a prime of the form 4n+3, and the seed is not 0, 1, or M-1, then the sequence of values z; has a period of 2n. (In particular, 22n+1 = 21.) We will need the fact from Section 3.9 that modulo any prime p, the ring Z, is cyclic, meaning there exists a generator g such that every nonzero element of the ring is some power of g. (c) In the original paper, they propose M to the product of two primes p = 4m +3 and q= 4n+3, each of the form 4n+3. What will be the period of the resulting generator? In particular, what if it is also true that q = 2p+1? The Hogwarts Quidditch League has four teams: Gryffindor, Hufflepuff, Ravenclaw, and Slytherin. In a given season there are six games, with each team playing each of the others once. Assume that a quidditch game cannot end in a tie and that each team is equally likely to win each game it plays. Using your favorite source of random bits (such as a coin, a stopwatch, or a computer), simulate ten full seasons of the league. (This might be by hand or by computer.) In how many seasons did one team finish undefeated? Calculate the probability that this happens, and compare this with your simulation. Consider the graph with a node for each five-letter English word, and an edge between two nodes if and only if their words differ in exactly one letter, such as moose and mouse. The five-letter edit game is to find a path in this graph from one word to another, or to find the shortest possible such path. Donald Knuth, in a computer search, found a path of length 20 from the word words to the word graph using only the 2000 most common five-letter English words. Can you duplicate this path, given the hint that the result of five edits from words is leapt, of ten edits is chose, and of fifteen edits is prone? The Blum-Blum-Shub generator produces pseudorandom bits as follows. We set a large natural M, set a natural seed ro, and define ₁+1 for each i as r(modM). We let each pseudorandom bit bi be the lowest-order bit of x,. Most of the motivation for this generator is beyond us at this point, but we can explore the choice of M, borrowing some work from Chapter 3. (a) Show that at least some primes of the form 4n+1 (for example, try starting with 17) are bad choices for M. (b) Show that if M is a prime of the form 4n+3, and the seed is not 0, 1, or M-1, then the sequence of values z; has a period of 2n. (In particular, 22n+1 = 21.) We will need the fact from Section 3.9 that modulo any prime p, the ring Z, is cyclic, meaning there exists a generator g such that every nonzero element of the ring is some power of g. (c) In the original paper, they propose M to the product of two primes p = 4m +3 and q= 4n+3, each of the form 4n+3. What will be the period of the resulting generator? In particular, what if it is also true that q = 2p+1? The Hogwarts Quidditch League has four teams: Gryffindor, Hufflepuff, Ravenclaw, and Slytherin. In a given season there are six games, with each team playing each of the others once. Assume that a quidditch game cannot end in a tie and that each team is equally likely to win each game it plays. Using your favorite source of random bits (such as a coin, a stopwatch, or a computer), simulate ten full seasons of the league. (This might be by hand or by computer.) In how many seasons did one team finish undefeated? Calculate the probability that this happens, and compare this with your simulation. Consider the graph with a node for each five-letter English word, and an edge between two nodes if and only if their words differ in exactly one letter, such as moose and mouse. The five-letter edit game is to find a path in this graph from one word to another, or to find the shortest possible such path. Donald Knuth, in a computer search, found a path of length 20 from the word words to the word graph using only the 2000 most common five-letter English words. Can you duplicate this path, given the hint that the result of five edits from words is leapt, of ten edits is chose, and of fifteen edits is prone?

Answer rating: 100% (QA)

Here are the steps to solve this problem a Primes of the form 4n1 are bad choices for M because for ... View the full answer