(Solved): Blum-Blum-Shub. Recall the BBS algorithm for generating pseudo random numbers: Let p and q be two l ...

Blum-Blum-Shub. Recall the BBS algorithm for generating pseudo random numbers: Let $p$ and $q$ be two large primes such that $p?q?3(\mathrm{mod}4)$ and let $n=p\times q.$ Choose a seed value $x_0$ that is relatively prime to $n$. The $i$ th pseudorandom bit is generated as $b_i=x_i\mathrm{mod}2$, where $x_{i+1}=x_i^2(\mathrm{mod}n)$. (a) Choose $p,q$ and $x_0$ that satisfy the requirements of BBS algorithm. (b) Write a code that received $p,q,x_0$ and integer $N$ as inputs and employs BBS method to generate $N$ bits. Hint: If you are using Python, you can use '\%' to perform mod operation. (c) Use the code you have written and test it with the parameters you have selected in part (a) to generate $N=10^6$ bits. Report the frequency of 0 s in your sequence. Also, report the frequency of the pair $(0,0)$ in your sequence. What is the expected value of this number if your sequence was completely random? Hint: To determine the frequency of the pair $(0,0)$ in a sequence $\left(b_1,\dots ,b_i\right)$, count how often $(0,0)$ appears in consecutive pairs. This is mathematically represented as $\#\left\{i:\left(b_i,b_{i+1}\right)=(0,0)\right\}$. Then, divide this count by the maximum possible number of such pairs in a sequence of length $n$, which is $n?1$. For instance, consider the sequence: $(1,0,0,0,1,1,0,1,0,0)\text{. }$ Here, the frequency of the pair $(0,0)$ is $\frac{3}{9}$.