**Section 2.1: Shift Ciphers and Modular Arithmetic**Practice HW from Barr Textbook (not to hand in) p.66 # 1, 2, 3-6, 9-12, 13, 15**Modular Arithmetic**• In grade school, we first learned how to divide numbers. Example 1: Consider Determine the quotient and remainder of this division and write the result as an equation.**The previous example illustrates a special case of the**divisionalgorithm which we state next. • Before stating this algorithm, recall that the integers are the numbers in the following set: Integers:**Division algorithm**• Let m be a positive integer (m > 0) and let b be any integer. Then there is exactlyone pair of integers q (called the quotient) and r (called the remainder) such that where .**A number of primary interest in this class will be the**remainder that we obtain the division of two numbers. We will find the remainder so often that we use a special term that is used to describe its computation. This is done in the following definition.**Definition**• We say that r is equal to b MOD m , written as b MOD m , if r is the integer remainder of b divided by m . We define the variable m as the modulus.**Example 2: Determine 25 MOD 7, 31 MOD 5,**26 MOD 2, and 5 MOD 7. Solution:**Note:**• In the division algorithm, the remainder r is non-negative, that is, . This fact means that when doing modular arithmetic that we will never obtain a negativeremainder. To compute b MOD m when b < 0 correctly, we must always look for the largest number that m evenly divides that is less than b. The next example illustrates this fact.**Example 3: Compare computing 23 MOD 9 with -23 MOD 9.**Solution:**Doing Modular Arithmetic For Larger Numbers With A**Calculator • To do modular arithmetic with a calculator, we use the fact from the division algorithm that and solve for the remainder to obtain**Truncated Quotient (chop digits to right of decimal)**• We put this result in division tableau format as follows: Remainder**Example 4: Compute 1024 MOD 37:**Solution:**Example 5: Compute 500234 MOD 10301**Solution:**Example 6: Compute -3071 MOD 107**Solution:**Generalization of Modular Arithmetic**• In number theory, modular arithmetic has a more formal representation which we now give a brief description of. This idea can be expressed with the following example.**Example 7: Suppose we want to find a solution**to the equation b MOD 7 = 4 Solution:**The numbers**from Example 7 that give a remainder of 4 MOD 7 represents a congruenceclass. We define this idea more precisely in the following definition.**Definition**• Let m be a positive integer (the modulus of our arithmetic). Two integers a and b are said to be congruent modulo m if a-b is divisible by m. We write (note the lower case “mod”)**Note**• The previous definition can be thought of more informally as follows. We say that if a and b give the sameintegerremainder when divided by m. That is, if r = a MOD m = b MOD m.**Example 8: Illustrate why .**Solution:**The last example illustrates that when the uppercase MOD**notation is used, we are interested in only the specific integer remainder when a number is divided by a modulus. The lowercase mod notation with the notation is used when we are looking for a set of numbers that have the same integer remainder when divided by a modulus. In this class, we will primarily use the MOD notation.***Note:**• When considering bMOD m, since , the only possible remainders are This causes the remainders to “wrap” around when performing modular arithmetic. This next example illustrates this idea.**Example 9: Make a table of y values for the**equation y = (x + 5)MOD 9 Solution:**Modular Equation Addition Prop.**• Solving equations (and congruences) if modular arithmetic is similar to solving equations in the real number system. That is, if then and for any number k.**Example 10: Make a list of five solutions to**mod 8 Solution:**Basic Concepts of Cryptography**• Cryptography is the art of transmitting information in a secret manner. We next describe some of the basic terminology and concepts we will use in this class involving cryptography.**Plaintext – the actual undisguised message (usually an**English message) that we want to send. • Ciphertext – the secret disguised message that is transmitted. • Encryption (encipherment) – the process of converting plaintext to ciphertext. • Decryption (decipherment) – process of converting ciphertext back to plaintext.**Notation**• represents all possible remainders in a MOD system, that is, • For representing our alphabet, we use a MOD 26 system**MOD 26 Alphabet Assignment**• Used to perform a one to one correspondence between the alphabet letters and the elements of this set.**Monoalphabetic Ciphers**• Monoalphabetic Ciphers are substitution ciphers in which the correspondents agree on a rearrangement (permutation) of the alphabet. In this class, we examine 3 basic types of monoalphabetic ciphers**Types of Monoalphabetic Ciphers**1. Shift Ciphers (covered in Section 2.1) 2. Affine Ciphers (covered in Section 2.2) 3. Substitution Ciphers (covered in Section 2.3)**Shift Ciphers**• If x is a numerical plaintext letter, we encipher x by computing the Enciphering formula for Shift Ciphers MOD 26, where k is in Here y will be the numerical ciphertext letter. *Note:k is called the key of the cipher and represents the shift amount.**Example 11: The Caesar cipher, developed by**Julius Caesar is a shift cipher given by MOD 26 Note that the key k = 3. MOD 26**Use the Caesar cipher to create a cipher**alphabet. Then use it to encipher the message “RADFORD”. Solution: To create the cipher alphabet, we substitute the MOD 26 alphabet assignment number for each letter into the Caesar shift cipher formula and calculate the corresponding ciphertext letter number as follows:**This gives the corresponding correspondence**between the plain and ciphertext alphabets Using the above table, we can encipher the message “RADFORD” as follows Hence, the ciphertext is “UDGIRUG” . █**In the last example we did not have to create the**entire plain and ciphertext alphabets to encipher the message. We could instead just used the shift cipher formula y = (x+3)MOD 26 directly. The Caesar cipher is just a special case of a shift cipher with a key of k = 3. In a general shift cipher, the key k can be any value in a MOD 26 system, that is, any value in the set**Example 12: Encipher the message “SEINFELD”**using a 12 shift cipher. Solution:**Deciphering Shift Ciphers**• Given a key k, plaintext letter number x, and ciphertext letter number y, we decipher as follows: y = (x + k) MOD 26**Deciphering formula for shift ciphers**x = (y – k) MOD 26 where y is the numerical ciphertext letter, x is the numerical plaintext letter, and k is the key of the cipher (the shift amount). *Note: In the deciphering shift cipher formula, – k MOD 26 can be converted to its equivalent positive form by finding a positive remainder.