$*$ Install the Python library $`$pycryptodome$`$ by executing the following in a code cell.

$```$

$!$pip install pycryptodome

$```$

$*$ Import some functions we will use by executing the following code. $($This will raise an error if $`$pycryptodome$`$ hasn't been successfully installed.$)$

$```$

from Crypto.Util.number import getPrime, getRandomNBitInteger

from sympy$.$ntheory import n$\_$order

from Lab$2\_$Helper import $($

only$\_$letters,

weave,

shift$\_$string,

add$\_$spaces,

to$\_$base$\_$b$,$

from$\_$base$\_$b

$)$

$```$

$*$ Paste in your code defining the $`$vigenere$`$ function from Lab $1.($It has been included all the necessary imports like $`$only$\_$letters$`,$ but feel free to add more if your $`$vigenere$`$ function depends on them.$)$

$*$ Paste the code defining the $`$naive$\_$dlog$`$ function.

$```$

def naive$\_$dlog$($g$,$ h$,$ p$)$:

output $=1$

for i in range$($p$-1)$:

output $=$ output$*$g$\%$p

if output $==$ h:

return i

return None

$```$

The $`$getPrime$`$ function imported above takes as input an integer $`$N$`$ and as output returns a random $`$N$`-$bit prime number. $($For example, $`37=32+4+1`$ written in binary is $`100101`,$ which is $6$ digits, so $`37`$ is a $6-$bit prime number. You can verify this by evaluating $`$to$\_$base$\_$b$(37,2)`$ and checking that the resulting list is length $6.$ The $`$from$\_$base$\_$b$`$ function goes in the opposite direction.$)$

$*$ Choose a prime $`$p$0`$ using the $`$getPrime$`$ function. $($See the next few instructions to help you decide how large the prime should be$.)$

$*$ Find a generator $`$g$0`$ for $$(\backslash$mathbb$\{$Z$\}\_\{$p$\_0\})^\{*\}$$$.($Hint$.$ Use the $`$n$\_$order$`$ function that we imported from SymPy$.$ Call $`$help$($n$\_$order$)`$ to see how this function works. What order do we need to have a generator? You will have to do some guessing$-$and$-$checking $($or better, use a $`$for$`$ loop, calling $`$break$`$ when you've found a generator$),$ but it shouldn't take many guesses before you find a generator.$)$

$*$ Call $`$naive$\_$dlog$($g$0,0,$ p$0)`,$ and time how long it takes using $`\%\%$time$`$ at the top of the cell. We already know that no discrete logarithm exists in this case $($why$?),$ so the point of this is just to see how long the naive discrete logarithm takes to run in the worst$-$case scenario.

$*$ We want a prime for which this naive discrete logarithm calculation takes $1-4$ seconds. If your prime takes an amount of time outside of this range, then change the values of $`$p$0`$ and $`$g$0`$ above until you find values for which it takes $1-4$ seconds.

$*$ Again using the getPrime function, find a prime $`$p$`$ which is $`20`$ bits larger $($add$,$ don't multiply$)$ than the prime $`$p$0`$ you found above.

$*$ As above, find a generator $`$g$`$ for $$(\backslash$mathbb$\{$Z$\}\_\{$p$\})^\{*\}$$$.$

$*$ We estimate that multiplying $`$p$0`$ by $`$M$`$ will multiply the amount of time the naive discrete logarithm takes by $`$M$`.$ Using this estimate, how many $*$days$*$ would you expect the naive discrete logarithm to take for $`$p$`?($Your answer should depend on $`$p$/$p$0`$ and on the number of seconds given by your timing computation above. $**$Do not$**$ try to run the naive discrete logarithm function on $`$p$`$ directly. Be sure your answer is in days, not in seconds.$)$