Fix a modulus m and use the affine cipher with key k1 a b

Question

1. Find φ (2007), φ (2008), and φ (b), where b is the integer obtained from the last four digits of your student number.

2. Find the smallest nonnegative integers x such that

(a) 7x ≡ 8 (mod 5);

(b) 9x ≡ 6 (mod 7);

(c) 5x ≡ 7 (mod 11).

3. Using the fact that 10 ≡ 1 (mod 9), resp. 10 ≡ -1 (mod 11), prove the following divisibility rules for integers in decimal notation:

(a) "Casting out nines", i.e., an integer is divisible by 9 if and only if the sum of its digits is divisible by 9. (b) Less well-known, but just as easy: An integer is divisible by 11 if and only if the alternating sum of its digits is divisible by 11. (Example: 11 | 1353 because 3 - 5+3 - 1 = 0, which is divisible by 11.)

4. (a) Encipher the word cryptography with the affine cipher with m = 26 and key k = (5, 9).

(b) Find the decryption function and decipher the result of (a).

5. Fix a modulus m and use the affine cipher with key k₁ = (a, b) to encrypt an element x; then encrypt the result with a key k₂ = (c, d). What is the resulting cipher? Given your answer, is security of the affine cipher with a given modulus m increased if one encryption is followed by a second encryption with a different key?

6. Suppose we work modulo 29 instead of modulo 26 for affine ciphers. How many keys are possible? What if we work modulo 30?

7. (a) Determine the number of bit permutations of the set {0, 1}ⁿ, n ∈ N.

(b) Determine the number of circular right shifts of {0, 1}ⁿ.

(c) Find a permutation of {0, 1}ⁿ that is not a bit permutation.

8. Let Σ be an alphabet. Show that the set Σ* together with concatenation is a monoid. Is this monoid a group?

Answer 1

As these questions are describing to smallest nonnegative integers 1. Discover f (2007), f (2008), and f (b), where b is the integer attained from the last 4 digits of your student number. 2. Discover the smallest nonnegative integers x such that (a) 7x = 8 (mod 5); (b) 9x = 6 (mod 7); (c) 5x = 7 (mod 11). 3. Using the fact that 10 = 1 (mod 9), resp. 10 = -1 (mod 11), prove the subsequent divisibility rules for integers in decimal notation: (a) "Casting out nines", for instance, an integer is divisible via 9 if and only if the sum of its digits is divisible by 9. (b) Less well-known, but just as easy: An integer is divisible via 11 if and only if the alternating sum of its digits is divisible via 11. (Example: 11 | 1353 as 3 - 5+3 - 1 = 0, which is divisible via 11.)