Prove that for any integers x and y, (x # y) mod n = (x

5 = 11 + 14. Show by computing each expression that 25 mod 6 = (11 mod 6 + 14 mod 6) mod 6

395 = 129 + 266. Show by computing each expression that 395 mod 4 = (129 mod 4 + 266 mod 4) mod 4

262 = 74 + 188. Show by computing each expression that 262 mod 13 = (74 mod 13 + 188 mod 13)mod 13

Prove that for any integers x and y, (x + y) mod n = (x mod n + y mod n)mod n

486 = 18 # 27. Show by computing each expression that 486 mod 5 = (18 mod 5 # 27 mod 5) mod 5

7067 = 191 # 37. Show by computing each expression that 7067 mod 8 = (191 mod 8 # 37 mod 8) mod 8

Prove that for any integers x and y, \((x \cdot y) \ \mathrm {mod} \ n = (x \ \mathrm {mod} \ n \cdot y \ \mathrm {mod} \ n) \ \mathrm {mod} \ n\)

Prove that for any integers x and y, (x # y) mod n = (x mod n # y mod n) mod n

Using the hash function of Example 51, which of the following Social Security numbers would cause a collision with 328356770, the Social Security number of that example? a. 060357896 b. 896137243 c. 712478993 d. 659027781

Find a set of five numbers in the range 30, 2004 that cause 100% collision using the hash function h(x) = x mod 13

Using a hash table of size 11 and the hash function x mod 11, show the results of hashing the following values into a hash table using linear probing for collision resolution: 1, 13, 12, 34, 38, 33, 27, 22

Using the completed hash table from Exercise 11, compute the average number of comparisons needed to perform a successful search for a value in the table. 13. When a computer program is compiled, the compiler

When a computer program is compiled, the compiler builds a symbol table for storing information about the identifiers used in the program. A scheme is needed to quickly decide whether a given identifier has already been stored in the table and, if not, to store the new identifier. A hash function is often used to locate a position in the table at which to store information about an item. For simplicity, assume that the items to be stored are integers, that the hash table can hold 17 items in positions 016, and that the hash function h(x) is given by h(x) = x mod 17. Linear probing is used for collision resolution. a. Using the hash function and collision resolution scheme described, store the sequence of values 23, 14, 52, 40, 24, 18, 33, 58, 50. Give the location in the table at which each is stored. b. After the table of part (a) has been filled, describe the process to search for 58 in the table. Describe the process to search (unsuccessfully) for 41 in the table.

Explain what problem can arise if an item stored in a hash table is later deleted.

A disadvantage of hashing with linear probing for collision resolution is that elements begin to cluster together in groups of adjacent array locations. Assume that you have a very good hashing function (it distributes elements evenly throughout the hash table). Start with an empty hash table of size t that will store data using linear probing for collision resolution. a. What is the probability of hashing the first element to location p (and storing it there, since it is the first item and there will be no collisions)? b. Once location p is occupied, what is the probability of storing the second item in location p + 1 (modulo the table size)? c. Once locations p and p + 1 are occupied, what is the probability of storing the third item in location p + 2 (modulo the table size)?

Generalize the answers to Exercise 15 to explain why using linear probing for collision resolution causes clustering.

Decode the following ciphertext messages that were encoded using a Caesar cipher with the given key. a. JUUBFNUUCQJCNWMBFNUU, k = 9 b. XAEWFVMPPMKERHXLIWPMXLCXSZIWHMHKCVIERHKMQFPIMRXLIAEFI, k = 4 c. IURSAYZGXJCOZNZNKQTOLKOTZNKROHXGXE, k = 6

Using a Caesar cipher, encode the following plaintext messages. a. ATTACK FROM BEYOND THE RIVER, k = 5 b. WE ARE SHORT OF SUPPLIES, k = 10 c. BADLY NEED AMMUNITION, k = 8

The following ciphertext message is intercepted; you suspect it is a Caesar cipher. Find a value of k that decodes the message, and give the corresponding plaintext. BUNNYWXFFNVJALQXWAXVNCXVXAAXF

The following ciphertext message is intercepted; you suspect it is a Caesar cipher. Find a value of k that decodes the message, and give the corresponding plaintext. EQQKAGAZRMOQNAAWPGPQ

Use the algorithm of Example 53 to compute the 1-bit circular left shift of the following binary strings (write the bit strings for x, p, q, and so on). a. 10011 b. 0011

Use the algorithm of Example 53 to compute the 1-bit circular left shift of the following binary strings (write the bit strings for x, p, q, etc.). a. 10110 b. 1110

Consider a “short form” of DES that uses 16-bit keys. Given the 16-bit key 1101000101110101 as input to a DES round that uses a circular left shift of 2 bits, what would be the key for the next round?

Describe how to perform a 1-bit right circular shift on a 4-bit binary string x using the left circular shift operation.

Using RSA encryption/decryption, let p = 5 and q = 3. Then n = 15 and w(n) = 4 # 2 = 8. Pick e = 3. a. Use the Euclidean algorithm to find the value of d. b. Encode T = 8 using the public key (n, e). c. Decode your answer to part (b) to retrieve the 8.

Why is the RSA encryption of Exercise 25 a poor choice?

Using RSA encryption/decryption, let p = 5 and q = 11. Then n = 55 and w(n) = 4 # 10 = 40. Pick e = 7. a. Use the Euclidean algorithm to find the value of d. (Hint: If the Euclidean algorithm produces an equation 1 = x # e + f # w(n)where the value of x is negative, add and subtract the product e # w(n) to the right side of the equation to get a positive value for d.) b. Encode T = 12 using the public key (n, e). c. Decode your answer to part (b) to retrieve the 12.

Using RSA encryption/decryption, let p = 23 and q = 31. Then n = 713 and w(n) = 22 # 30 = 660. Pick e = 17. a. Use the Euclidean algorithm to find the value of d. b. Encode T = 52 using the public key (n, e). c. Decode your answer to part (b) to retrieve the 52

a. All n people in a group wish to communicate with each other using messages encrypted with DES or AES. A different secret key must be shared between each pair of users. How many keys are required? b. All n people in a group wish to communicate with each other using messages encrypted with a public key encryption system. How many keys are required?

Computer users are notoriously lax about choosing passwords; left to their own devices, they tend to pick short or really obvious passwords. At Simpleton University, passwords must contain only lowercase letters, and the campus computer system uses an (unrealistically simple) cryptographic hash function given by the following algorithm: 1. Letters in the password are converted to an integer equivalent (a S 1, b S 2, and so on). 2. In the result of step 2, all individual digits are added (for example, 17 becomes 1 + 7) to give an integer value x. 3. h(x) = x mod 25 Joe Hack has managed to steal the password table, and he notices that there is a password entry of 20 for bsmith. Joe decides to try to hack into the system as bsmith by guessing bsmiths password. Can you guess bsmiths password?

a. The ISBN-10 of the sixth edition of this book is 0-7167-6864-C where C is the check digit. What is the check digit? b. What is the ISBN-13 of the sixth edition?

A bookstore placed an order for 2000 copies of Harry Potter and the Deathly Hallows, the seventh and final volume in the hugely popular Harry Potter series by J. K. Rowling. When placing the order with the publisher, the ISBN-13 978-0-545-01022-5 was used. Is this correct?

Given the 11 digits 02724911637, compute the check digit for the UPC-A code.

A taxpayer wants his tax refund to be deposited directly to his bank. He enters the banks routing number, including the check digit, as 025107036 Is this routing number correct?

a. Write an algorithm to decompose a four-digit integer into the ones, tens, hundreds, and thousands digits. b. Apply this algorithm to decompose the integer 7426

The following quilt image is based on addition modulo n for what value of n?

Prove that if x y (mod n) and c is a constant integer, then xc yc (mod n).

Exercises 37–41 involve a proof of step 7 of the RSA method. This exercise explores the converse of Exercise 37, which is the issue of cancellation under congruence modulo n. In other words, if \(x c \equiv y c(\bmod n)\) for some constant integer c, is it then true that \(x \equiv y(\bmod n)\) ? Not always, as it turns out. a. Prove that if \(\operatorname{gcd}(c, n)=1\), then \(x c \equiv y c(\bmod n)\) implies \(x \equiv y(\bmod n)\). b. Prove that \(x c \equiv y c(\bmod n)\) implies \(x \equiv y(\bmod n)\) only if \(\operatorname{gcd}(c, n)=1\). To do this, it is easier to prove the contrapositive: If \(\operatorname{gcd}(c, n) \neq 1\), then there exist integer values x and y for which \(x c \equiv y c(\bmod n)\) but \(x \not \equiv y \bmod n\). (Hint: Suppose \(c=m_1 k\) and \(n=m_2 k\) with \(k>1\). Consider \(x=m_2 k\) and \(y=m_2\).) c. Find values for x, y, c, and n where \(x c \equiv y c(\bmod n)\) but \(x \not \equiv y(\bmod n)\).

If p is a prime number and a is a positive integer not divisible by p, then ap1 1(mod p) 444 Relations, Functions, and Matrices Section 5.6 The Mighty Mod Function 445 This result is known as Fermats little theorem (as opposed to the very famous Fermats last theorem mentioned in Section 2.4). Let S = 50, a, 2a, ,(p 1)a6, T = 50, 1, 2, , (p 1)6. Let f be given by f(ka) = (ka) mod p; that is, f computes the residue modulo p. a. Prove that f is a one-to-one function from S to T. b. Prove that f is an onto function. c. Prove that 3a # 2a c(p 1)a4 mod p = (p 1)! mod p d. Prove that ap1 1 (mod p) e. Let a = 4 and p = 7. Compute the set of residues modulo p of 54, 8, 12, , 246. f. Let a = 4 and p = 7. Show by direct computation that 46 1(mod 7).

Let m1, m2, , mn be pairwise relatively prime positive integers (that is, gcd(mi , mk) = 1 for 1 i, k n, i k), let m = m1m2cmn, and let a1, a2, c, an be any integers. Then there is an integer x such that x a1 (mod m1) x a2 (mod m2) ( x an (mod mn) and any other integer y that satisfies these relations is congruent to x modulo m. This result is known as the Chinese remainder theorem (based on work done by the Chinese mathematician Sun-Tsu in the first century ad). The following steps will prove the Chinese remainder theorem. a. Let s and t be positive integers with gcd (s, t) = 1. Prove that there exists an integer w such that sw 1 (mod t). b. For each i, 1 i n, let Mi = mmi. Prove that gcd(Mi , mi ) = 1. c. Prove that there is an integer xi such that Mi xi 1 (mod mi ) and ai Mi xi ai (mod mi ). d. Prove that akMk xk 0 (mod mi ) for all k i. e. Let x = a1M1x1 + a2M2x2 + c+ anMn xn. Prove that for 1 i n, x ai (mod mi ). f. Let y be such that y ai (mod mi ), 1 i n. Prove that x y (mod m). (Hint: Use the fundamental theorem of arithmetic and write m as a product of distinct primes, m = pk1 1 pk2 2 pkt t ).

The remaining step in the proof of the RSA algorithm is to show that if d # e 1 mod w(n), then T ed mod n = T. a. Prove that T ed can be written as T(T p1 ) k(q1) or as T(T q1 ) k(p1) for some integer k. b. Prove that if T is not divisible by p, then T ed T (mod p), and if T is not divisible by q, then T ed T (mod q). c. Prove that if p 0 T, then T ed T (mod p) and T is not divisible by q, so T ed T (mod q) by part (b). d. Prove that if q 0 T, then T ed T (mod q) and T is not divisible by p, so T ed T (mod p) by part (b). e. From parts (b)(d ) T ed T (mod p) and T ed T (mod q) in all cases. Prove that Ted mod n = T.