Download the .ipynb file for this notebook, and place your solutions where indicated (you can use multiple cells for each problem). Name the file hw02.ipynb (you do not need to include your netid in the title). Then upload it to Blackboard as Homework 2 in the Assignments tab. See Collaboration Policy in Homework section of course webpage (it's the same as it was for HW01). Please include comments in your code to make it easier to read.
Write a function that takes as input an integer $n$ and returns its factorization into prime numbers. The output should be a list of the prime factors, with each prime $p$ appearing $k$ times in the list where $k$ is the largest power of $p$ such that $p^k$ divides $n$. The order of the elements of the list does not matter. For instance, if $n=12$, any of [2,2,3], [2,3,2], or [3,2,2] would be vaild outputs. Do not use the built-in factor function. Test your function on $2^{22}-1, 2^{23}-1$, and $2^{24}-1$.
# Put your solution here (you can add more cells using the Insert menu)
(a) Write a function that takes as input a string of characters, and returns the characters in reverse order (either as a list of characters, or as a string). Try your function on "MADWARWOLF". It should return "FLOWRAWDAM" (or a list of these characters).
(b) Write a function that takes as input a string of characters, and applies the above reverse cipher, followed by a shift (Caesar) cipher like the one we did in class (shifting by an amount of your choice). How hard would it be to break this combination cipher?
# Solution here
I made a string of capital letters by starting with some lyrics of a song written in English and stripping out all spaces and punctuation. I then encrypted this string with the shift (Caesar) cipher, obtaining the string below. What string did I start with, and what key did I use?
EVMVIKYFLXYKZUSVFERSFRKZKJRSZXSCLVNRKVIPIFRUGFJVZUFECFFBRKDVEVMVIKYFLXYKZUJVVKYVURPNYVERSZXSFRKTFDZEXDPNRP
# Solution here
Find several paragraphs of text written in English (eg from a book, magazine, news article, email exchange, etc). Strip out all non-letter characters (spaces, punctuation, numbers, etc), and convert all remaining letters to upper-case. Call this string CORPUS1. Ideally it should have at least 1000 characters. Determine the relative frequency of each letter in CORPUS1. Your output should be a list of the frequencies of each of the 26 letters.
# Solution here
(a) Convert CORPUS1 from above into a list of integers between 0 and 25 by taking each character to its place in the alphabet, starting with 0. For example "ZAP" would go to [25,0,15].
(b) Starting with a different collection of paragraphs from a similar source, generate a new CORPUS2 in a similar way. Convert CORPUS2 into a list of integers, as you did for CORPUS1.
(c) Truncate the longer of the two lists you created above so that they become the same length. Now subtract the first list from the second element-wise modulo 26. For instance if the two lists were [25,0,15] and [2,0,1], the new list would be [3,0,12]. What are the relative frequencies of each of the numbers 0,...,25 in this list?
# Solution here
(a) Take two English messages consisting of capital letters with no spaces or punctuation, each the same length of about a paragraph. Encrypt both messages using a one-time pad, using a different randomly chosen key for each. Now convert each encrypted message into a list of integers, exactly as in parts (a) and (b) of the previous problem. Subtract one list from the other element-wise modulo 26, as in the previous problem. What are the relative frequencies of each of the numbers 0,...,25 in the resulting list?
(b) Repeat part (a) above with the same two messages, but this time encrypt them with the same key (randomly chosen, and different from the two used previously). Do the same subtraction process as in (a). What are the relative frequences of each of the numbers 0,...,25 in the resulting list?
(c) Do parts (a), (b), together with the results from Problem 5, suggest a way to test whether the key for a one-time pad has been re-used based only on a collection of encrypted messages?
# Solution here