Question 5: LCM from a prime factorisation (ILO 1, 2; 2 marks)

You have learned how to calculate lcm(a, b) using the prime factorisations of a and b. Your task is to complete the stub function lcm(a, b) to implement this behaviour. In your solution you should use the Python Counter class to represent a multiset, and make use of the included helper function prime_factors(n) to generate a list of prime factors for each input.

Question 7: Shift and Flip Cipher (ILOs 1, 2; 3 marks)

Background Information

We will cover relevant encryption techniques in Week 10. If you’d like to explore further you can read about the simple Caesar shift cipher and a more complex version that has similarities to the approach described below, but both articles go into more detail you will need to approach this assignment question, and are not required reading in order to successfully complete the question.

A shift cipher encrypts each letter of a message by shifting the letter through an agreed alphabet by a particular number of steps (mod the length of the alphabet used). One improvement on this is to use a sequence of shift values, so different shifts are used for different letters in the message. This is the basis of the Vigenère cipher. The key is typically shorter than the message, so to encrypt a message the key is aligned with the message text, repeating it as many times as necessary. Here is an illustration when the agreed alphabet is ‘A’, ‘B’, …, ‘Z’ and the encryption key is (2,4,6):

message E X A M P L E
aligned key 2 4 6 2 4 6 2
ciphertext G B G O T R G
In the above, the first letter in the message, ‘E’ (= 4), is shifted by 2 places to ‘G’ (= 6), while ‘X’ (= 23) is shifted by 4 places with wrap around to ‘B’ (= 1), ‘X’ → ‘Y’ → ‘Z’ → ‘A’ → ‘B’. Decryption uses the same key but subtracts the shift instead of adding it. Like many similar encryption techniques, encryption and decryption are processes that deal with numbers. For a single letter then, we can think of encryption as letter → numerical position in agreed alphabet → encrypted number → encrypted letter.

We can build on this system by flipping the direction of the shift every flip steps, essentially making our key a logical pair of (key, flip). If we consider the example above, using the same key (2, 4, 6) and a flip of 2 then the encryption operation would be:

message E X A M P L E
aligned key 2 4 -6 -2 4 6 -2
cipher text G B U K T R C
We will call this the Shift and Flip Cipher.

The flip can be disabled by selecting a value at least as long as the message. A flip of zero must not be used (dealing with it would add unnecessary complication to your code).

Supplied code and your tasks

There is a partial implementation of this cryptosystem in the Python script. It operates by converting text into a sequence of numbers then doing the the encryption (or decryption) process on the sequence before converting the modified sequence of numbers back into text. It currently comprises four functions:

indices(text, symbols=DEFAULT): Converts the characters in the string text into a list of their numerical positions within the (optionally-supplied) sequence of symbols. The variable DEFAULT is a string of characters suitable for basic messages (it contains 27 characters, A-Z plus space), already defined in the script file, and is used here as a default value for symbols. You must not modify this function
text(indices, symbols=DEFAULT): Reconstructs a string using the characters at the given indices (positions) in symbols. You must not modify this function
encrypt(message, key, flip, symbols=DEFAULT): Encrypts the message using a multiple shift cipher using the tuple of shift values in key, changing the direction of shifts after every flip characters, with reference to the sequence of allowed symbols. You will complete the implementation of this function
decrypt(cipher, key, flip, symbols): Decrypts the cipher text using a multiple shift cipher using the tuple of shift values in key, changing the direction of shifts after every flip characters, with reference to the sequence of allowed symbols. You will implement this function
Note: The examples above assumes 26 symbols, while the provided code offers a sample set of 27 symbols, so encrypting EXAMPLE with (2,4,6) and 2 will not produce identical output. You should work out on paper what you are expecting to see when you encrypt a message to test if your implementation is working.

Your tasks are to:

Define some test cases for encryption and decryption, explaining your choices. There are two separate lists for these in the script. Each test case is a 5-tuple comprising the 4 inputs to the encrypt or decrypt function and the expected result. Although you can call encrypt with just three arguments (and it will assume DEFAULT is the sequence of symbols to use), the test cases require you to explicitly specify the value for the symbols parameter (so that the final element in the test tuple is unambiguously the expected result).

Your test cases should be thorough, evaluating both silly and more realistic inputs, although the data passed must be the correct type. You are testing expected behaviour, not trying to crash the code.

Complete the implementation of encrypt: To implement the encryption system without the flip only one line of code needs to be changed. Adding the flip requires some additional lines of code, but none of them is complex.

Advice: Get your implementation working without using the flip first. Then work on adding the flip functionality

Implement decrypt: There are various ways this can be completed. A correctly-functioning implementation will earn at least 0.5/1. A version that is compact, either making use of encrypt or some other function that you define, will be eligible for the full mark. You are allowed to alter the implementation of encrypt as part of any attempt to make decrypt compact, but the interface to both (their list of parameters) must not be altered.

How your assignment is assessed

Your handwritten maths answers will be assessed entirely by a member of the teaching team, with some feedback given where the wrong answer was reached or wrong approach taken.

Your submitted Python script will be assessed initially by a Python program that will execute your code and check the values generated by your answers against the expected results. This produces an Excel spreadsheet named AssessmentReport.xlsx with columns containing the expected result, the actual result produced by your code, the score achieved for that question (and maximum score possible), and any feedback explaining the score.

Next, a human assessor will inspect your submission and adjust the computer-based assessment accordingly: code that produced the wrong value but is close to correct will have some marks restored; code that produced the correct answer but did so incorrectly may have marks reduced. The assessor will add further feedback to the assessment report as needed.

You can download the Assessment Report from MyLO: go to Assignments then click feedback link in the Evaluation Status column. View it in Excel, Numbers or another spreadsheet program.

Complete Answer: