Purpose

Random number generators play a very important role in cryptography as they help to generate random, or pseudo$-$random, numbers. The textbook presents pseudorandom number generators on page $35.$ Your objective is to implement a pseudorandom number generator and then analyze its output for randomness.

Instructions

The linear congruential generator works as follows:

si$+1=$ a $*$ si $+$ b mod m$,$ i $=0,1,..$

where a$,$ b$,$ and m are integer constants.

Ideally, we would like these generators to be unpredictable, meaning given n consecutive output bits of the stream, it is computationally infeasible to predict the next bit with a greater than $50\%$ chance of success.

To complete the assignment, do the following:

$1)$Use Python to implement the linear congruential generator, generating an output sequence of exactly N binary digits in length.

This sequence should be derived from a keystream as explained in the last parts of section $2\mathrm{.}2\mathrm{.}1$ on pages $35-36$ in the textbook. Essentially, you generate a number of keys and then string them together, in binary format, to generate your binary sequence of N digits. So a key stream such as si$,$ si$+1,...$si$+$n$-1$ that is N binary digits in length is generated.

You MUST use the book values for the seed, a$,$ b and m $($on page $35).$

Your key stream should ideally be fairly long so that you can provide statistically reasonable answers to questions $3$ and $4$ below. A keystream of exactly N digits is required in this assignment, with N $=1000.$

Note that there are many ways to convert decimal to binary in python; a simple method is to output each integer key as a binary string and then concatenate those strings together:

num $=100$; # decimal integer number $100$

numString $=$ bin$($num$)$ # int to binary string conversion

print$($numString$[2$:$])$ # should print the binary string $1100100,$ after stripping off the leading $\text{'}0$b$\text{'}$

$2)$ Save the output sequence to a file called yourlastname$\_$output.txt$.$

$3)$ Report the number of $1\text{'}$s and $0\text{'}$s in this sequence. How do these numbers compare?

$4)$ Consider the sequence $"01".$ How many times does this substring occur in your output sequence? How many times would you expect it to occur in a truly random output sequence?

Submission

Please submit your answers as a $.$zip file. The following items should be included in the $.$zip file:

Python source files for your code

The yourlastname$\_$output.txt file

A text document that has your answers$/$comments to questions $3$ and $4$