$*$ Write a function $`$prop$\_$div$`$ using the following template.

$>$ Input: a list of integers $`$X$`$ and a modulus $`$m$`$

$>$ Output: the proportion of integers in $`$X$`$ which are divisible by $`$m$`$

$>$

$>$ For example, $`$prop$\_$div$([3,5,8,9,10],3)`$ should be equal to $`0\mathrm{.}4`,$ because $2$ out of $5$ of these integers are divisible by $3.$

$```$

def prop$\_$div$($X$,$ m$)$:

n $=$ len$($X$)$

t $=0$ # Eventually t will be the number of integers divisible by m in X

for x in X:

if x$\%???==???$:

t $=$ t$+1$

return $???$ # Return the proportion, not t$.$

$```$

$*$ Write a function $`$key$\_$length$\_$kasiski$`$ to predict the key length using the following template. $($Recall that we introduced the $`$kasiski$\_$diffs$`$ function above.$)$ The idea is to find for which key length value, from $`$key$\_$start$`($inclusive$)$ to $`$key$\_$end$`($exclusive$),$ is the highest proportion of gaps between repeated trigrams divisible by that key length. The parameters $`$top$\_$value$`$ and $`$top$\_$key$`$ represent the current highest proportion and the current best key length, respectively.

Feel free to rewrite this if you would like to use a more elegant$/$Pythonic approach to find the best key length, as long as it is still using the $*$Kasiski method$*.($If I were doing this in Math $10,$ I think I would make a pandas Series $`$prop$\_$ser$`$ with values equal to the proportions and keys equal to the key lengths, and then I would find the best key length by using $`$prop$\_$ser.idxmax$()`.)$

$```$

def key$\_$length$\_$kasiski$($Y$,$ key$\_$start$=7,$ key$\_$end$=12)$:

diffs $=$ kasiski$\_$diffs$($Y$)$

top$\_$value $=0$

top$\_$key $=0$

for k in range$($key$\_$start, key$\_$end$)$:

prop $=$ prop$\_$div$($diffs$,$ k$)$

if $???>???$:

top$\_$value $=$ prop

top$\_$key $=$ k

return $???$ # Return the key length which yields the highest value

$```$

$*$ Test your function by evaluating the following. The output should be $`7`.$

$```$

Y $=\text{'}\text{'}\text{'}$zpgdl rjlaj kpylx zpyyg lrjgd lrzhz qyjzq repvm swrzy rigzh

zvreg kwivs saolt nliuw oldie aqewf iiykh bjowr hdogc qhkwa

jyagg emisr zqoqh oavlk bjofr ylvps rtgiu avmsw lzgms evwpc

dmjsv jqbrn klpcf iowhv kxjbj pmfkr qthtk ozrgq ihbmq sbivd

ardym qmpbu nivxm tzwqv gefjh ucbor vwpcd xuwft qmoow jipds

fluqm oeavl jgqea lrkti wvext vkrrg xani'$\text{'}\text{'}$

key$\_$length$\_$kasiski$($Y$)$

$```$

$*$ Write a function $`$coincidence$\_$mean$`$ using the following template. $($Note$.$ Base Python does not have a built$-$in mean or average function, but it does have a built in $`$sum$`$ function.$)$

$>$ Inputs: a string $`$Y$`$ and an integer $`$m$`.$

$>$ Output: a real number

$```$

def coincidence$\_$mean$($Y$,$ m$)$:

coinc$\_$list $=[]$

for i in range$($m$)$:

s $=$ # Get the characters in $`$Y$`$ at integer positions $???$ modulo $???$

c $=$ # Compute the Index of Coincidence for $`$s$`$ using the $`$ind$\_$co$`$ function

coinc$\_$list.append$($c$)$

return $???$ # Return the mean value of $`$coinc$\_$list$`$

$```$

$*$ Write a function $`$key$\_$length$\_$coincidence$`$ to predict the key length using the following template.

Again, feel free to rewrite this if you would like to use a more elegant approach, as long as it is still using the $`$coincidence$\_$mean$`$ function from above.

$```$

def key$\_$length$\_$coincidence$($Y$,$ key$\_$start$=7,$ key$\_$end$=12)$:

top$\_$value $=0$

top$\_$key $=0$

for k in range$($key$\_$start, key$\_$end$)$:

mean $=$ coincidence$\_$mean$(???,???)$

if $???>???$:

top$\_$value $=???$

top$\_$key $=???$

return $???$ # Return the key length which yields the highest value

$```$

$*$ Test your function by evaluating the following. The output should again be $`7`.$

$```$

Y $=\text{'}\text{'}\text{'}$zpgdl rjlaj kpylx zpyyg lrjgd lrzhz qyjzq repvm swrzy rigzh

zvreg kwivs saolt nliuw oldie aqewf iiykh bjowr hdogc qhkwa

jyagg emisr zqoqh oavlk bjofr ylvps rtgiu avmsw lzgms evwpc

dmjsv jqbrn klpcf iowhv kxjbj pmfkr qthtk ozrgq ihbmq sbivd

ardym qmpbu nivxm tzwqv gefjh ucbor vwpcd xuwft qmoow jipds

fluqm oeavl jgqea lrkti wvext vkrrg xani'$\text{'}\text{'}$

key$\_$length$\_$coincidence$($Y$)$

$```$

$*$ Paste in and execute the code for your $`$shift$\_$decrypt$`$ function from Lab $0.$

$*$ Write a function $`$find$\_$shifts$`$ using the following template.

$>$ Inputs: a Vigen$$re ciphertext string $`$Y$`$ and a key$-$length $`$k$`$

$>$ Output: a list of shift amounts $`$shifts$`$

$```$

def find$\_$shifts$($Y$,$ k$)$:

shifts $=[]$

for i in range$($k$)$:

s $=$ # Get the characters in $`$Y$`$ at integer positions $???$ modulo $???$

X$,$ m $=$ shift$\_$decrypt$($s$)$ # We only care about the shift amount $`$m$`$

shifts.append$($m$)$

return shifts

$```$