$3.[10$ points$]$ Implementation and Analysis of LFSR Keystream Generation.

Implement these functions:

$($a$)$ KeystreamGen$($k$,$ d$,$ n$),$ which generates the first

$$

n characters

$$

$1$

$$

$2$

$...$

$$

$$

z

$1$

$$

z

$2$

$$

$...$z

n

$$

of the LFSR keystream defined by the key

$($

$$

$,$

$$

$)$

$($k$,$d$).$

$($b$)$ FindPeriod$($k$,$ d$),$ which determines the period of the LFSR keystream defined by the key

$($

$$

$,$

$$

$)$

$($k$,$d$).$

$($c$)$ ComputeProb$($t$),$ which computes the probability that a randomly$-$chosen LFSR keystream defined by a recurrence of degree

$$

t has order as large as possible.

Hint:

i$.$ I don't care if your implementation is efficient. ii$.$ A recurrence of degree

$$

t is defined by two parameters: the initial conditions

$$

in

$$

$2$

$$

k in Z

$2$

t

$$

$,$ and the coefficient vector

$$

in

$$

$2$

$$

d in Z

$2$

t

$$

which satisfies

$$

$0$

$=$

$1$

d

$0$

$$

$=1.$

Using these tools:

$($a$)$ Determine the period of LFSR keystream arising from the following keys

$($

$$

$,$

$$

$)$

$($k$,$d$)$:

i$.$

$$

$=$

$11001111010011111111$

k$=11001111010011111111,$

$$

$=$

$11000010001000110100$

d$=11000010001000110100$

ii$.$

$$

$=$

$01010100001001000010$

k$=01010100001001000010,$

$$

$=$

$11100100110101100001$

d$=11100100110101100001$

iii.

$$

$=$

$10011011000111110101$

k$=10011011000111110101,$

$$

$=$

$11010101000000001110$

d$=11010101000000001110$

$($b$)$ Compute the probability that a randomly$-$chosen key

$($

$$

$,$

$$

$)$

$($k$,$d$),$ which defines a recurrence of degree

$$

t $($so

$$

$,$

$$

in

$$

$2$

$$

k$,$d in Z

$2$

t

$$

and

$$

$0$

$=$

$1$

d

$0$

$$

$=1),$ yields a keystream of maximal order, for

$$

$=$

$2$

$,$

$3$

$,$

$4$

$,$

$5$

$,$

$6$

$,$

$7$

t$=2,3,4,5,6,7.$