You are tasked with building two fully working programs. The frst will be used to calculate an approximate value for PI, the second will allow an end to generate encrypted text (or ciphertext) using the Hill Cipher.
Notes:
Standard penalties will be applied to work that is submitted late. The time of submission as displayed by the moodle will be the reference point for lateness.
You must submit a single zip fle (named studentname_studentnumber) that contains two c++ fles containing your MPI source code. Code that fails to compile will incur a penalty of 30%. The accepted compression formats for your archives are zip/rar/7z any format outside of this will incur a 10% penalty.
For the purposes of this assignment you will only need four standard header fles
All work submitted must be your own only, if plagiarism is detected both parties will be awarded a grade of 0.
Part I: Finding Pi (50%)
You are asked to create a program that will be used to calculate an approximate value for PI. This program will utilise the Master/Slave Arrangement.
The formula used to calculate PI is as follows:
The integral should be approximated, over the number of intervals specifed by the end user. If for example, the number of intervals is 10, the calculation would involve the following:
Please Note:
The more intervals used in the calculation the more accurate the value of PI will be.
● The workload should be distributed over an appropriate number of processes
● The Master (Process 0) should inform the slaves of the number of intervals to be used in the calculation, each slave that receives this value should interpret it correctly and perform an appropriate calculation.
● The values computed by each process should be reduced to a single value using a reduction operation.
● Test your program for the following number of intervals.
i. 10
ii. 100
iii. 1,000
iv. 100,000
v. 1,000,000
You may want to use these MPI routines in your solution:
– MPI_Bcast
– MPI_Reduce
Part II: Hill Cipher (50%)
Encryption is defned as the translation of data into a secret code. Unencrypted data is called plain text; encrypted data is referred to as cipher text.
● As part of this exercise you will convert plaintext into ciphertext using the Hill Cipher.
● Encryption using the Hill Cipher is based on Matrix Multiplication
Hill Cipher Example
Using a keyword of “Hill” encrypt the plaintext “text” using the Hill Cipher
Step 1
● Convert the keyword into pairs of letters (HI, LL) and form a matrix
● Convert each letter in Matrix into its numerical equivalent
Step 2
● Convert the plaintext into pairs of letters (TE, XT) and form a matrix
● Convert each letter in Matrix into its numerical equivalent
Step 3
● Multiply the two matrices together (i.e. keyword and plaintext matrices) as follows:
Step 4
● Get Mod 26 of each value in the resultant matrix
=
Step 5
● Map each value in the matrix generated in Step 4 to a letter in the alphabet.
Therefore, the ciphertext is: vogd
● If the process of matrix multiplication is divided in the right way the task
● can be parallelised efciently.
● In this assignment, you will need to multiply two matrices together using an appropriate methodology (the strip method for example)
● You will generate three matrices Matrix P (plaintext matrix), Matrix K (keyword matrix) and Matrix C (Ciphertext Matrix) that represent the three diferent matrices.
● The keyword matrix, Matrix K must be a square matrix (e.g. 2×2, 3×3)
● Matrix C stores the result of multiplying Matrix P by Matrix K.
Please Note:
● You cannot simply multiply two matrices together using a single node.
● You must divide up the work amongst participating nodes
One possible approach to Matrix Multiplication is as follows
a. Pass a diferent column of the plaintext Matrix to each participating node b. Pass a full copy of the Keyword Matrix to each participating node
c. Get each participating node to multiply its strip of the plain text Matrix, with the keyword Matrix.
d. Finally, the results from each node are sent back to the coordinator and reassembled into a single matrix.
Reference Links
Hill Cipher
http://practicalcryptography.com/ciphers/hill-cipher/
Matrix Multiplication
https://www.mathsisfun.com/algebra/matrix-multiplying.html
Tasks
5% Write a main method that will initialise MPI, fgure out the world rank and world
size. Rank 0 should be the coordinator while all other ranks should be
participants. Then fnalise MPI and return a status of 0 to the OS
15% Add a minimum of three appropriate methods to your code, for example:
i. genKeyMatrix: converts the keyword used for encryption into Matrix form
ii. showMatrix: displays the contents of a Matrix on the console
iii. multStrip: multiply a Strip of the plaintext Matrix with the keyword Matrix.
80% Write coordinator and participant methods to implement the following:
● Read in the plaintext and keyword from the console
● Generate a series of digraphs from the plaintext
● If the number of letters in the plaintext is not divisible by 2, it must be padded with fller letters so that it is divisible by 2
● e.g. If the plaintext was BOOKS this contains 5 letters so would be padded as follows: BOOKSX
● Generate a Matrix from the digraphs, and convert each letter into its numerical equivalent (e.g. A=0, B=1, C=2 etc.)
● If the keyword generates a non-square matrix, either pad it with fller letters) OR inform the user to choose another keyword.
● Generate a series of digraphs from the keyword and combine to form a matrix
● Convert each letter in the matrix to its numerical equivalent
● Distribute the keyword in its entirety to all participants
● Distribute a strip of the plaintext matrix to each participant
● Each participant should multiply the keyword matrix and the strip of the plaintext matrix together
● All participants should take part in a GATHER operation (or similar) to send the result of their calculation back to the coordinator
● Reassemble the strips into a single Matrix, called the Ciphertext Matrix
● Get Mod 26 of each of the values within the Ciphertext Matrix, and map each of the resultant values to a letter in the alphabet.
● Print the Plaintext, the keyword and the result of encrypting the plaintext using the keyword, for example:
○ Plaintext: Text
○ Keyword: Hill
○ Ciphertext: Vogd
