To beat a frequency attack, there are several methods described here. All modern symmetric ciphers are block ciphers, which are ciphers where the encryption happens in blocks of bits.
More about dictionaries. The python dictionary tutorial is decent, but this overview is a nice walkthrough of dictionaries and is similar to what I did in class.
Memoization is a technique to speed up a time consuming function by using a dictionary to keep around the result of the function. We will write code to compute the factorial. (This is already implemented in python but it is a good example.) We are going to keep around a dictionary, where the keys are going to be the input and the values the result of the factorial.
# Start with nothing computed yet
factorial_memo = {}
def factorial(n):
# If the factorial has already been computed, just return it
# We check if the factorial has been computed already by checking
# to see if the key n exists in the memo
if n in factorial_memo:
return factorial_memo[n]
# Compute the factorial (note the n+1 to range, since range
# returns a list of up to but not including n+1).
result = 1
for i in range(2,n+1):
result *= i
# Now we store this in the memo
factorial_memo[n] = result
return result(There is an easy optimization to the above code: when computing n! we don't need to take the product all the way down to one, we could check if an already computed smaller value exists in the memo. For example, if 5! was in the memo and we are asked to compute 7!, we could lookup the value of 5! in the dictionary and multiply that by 6 and 7. Think about how you would modify the above code to implement this.)
We can test this out using the time module, in particular the time.time function which returns the number of seconds as a floating point (so fractional seconds) that have elapsed since the Unix Epoch. (I should point out that programming languages keep time like this because it is easier to work with time as a single number, the number of seconds since Jan 1, 1970 00:00:00 UTC. We can do things like subtract two times to get the elapsed seconds and many other calculations are straightforward. Also no daylight savings jumps, no leap seconds. Programming languages like python (in the time module) then provide a conversion function to human readable strings which is used before displaying the time to the user. This conversion function needs to know all about time zones and leap years and daylight savings and leap seconds. But the majority of the manipulation of time in a program is via a single number.)
In any case, you can see the current time via
import time
print(time.time())We can use this to test our factorial program.
import time
t1 = time.time()
factorial(20000)
t2 = time.time()
print("Time 1: ", t2 - t1)
factorial(20000)
t3 = time.time()
print("Time 2: ", t3 - t2)
# Just to see how big the number is
print(factorial(20000))For me, the first time runs in around 0.1 seconds and the second runs around 0.00004 seconds.
You have been given the following lists of students and their scores
names=['Joe', 'Tom', 'Bob', 'Emily', 'Sue']
scores=[10, 23, 13, 18, 12]make_scores_dict that takes as arguments two lists and returns a dictionary with the names as the key and the scores as the values.make_scores_dict with the above two lists and store the dictionary return value in a variable.