Outline for April 9, 1997

1. Greetings and Felicitations
   1. For NTU: All homework is due 1 week after the due date; I'll put this explicitly on future assignments
2. Solving ax mod n = 1:
   1. { r₁, ...,r_PHI(n)} reduced set of residues
   2. by definition, { ar₁ mod n, ..., ar_PHI(n) mod n} is same set
   3. So, PI(ar_i mod n ) = PI r_i (product from 1 to PHI(n))
   4. This means (a^PHI(n) mod n) PI r_i = PI r_i, giving a^PHI(n) mod n = 1.
   5. Ex: a = 5, n = 7; 5x mod 7 = 1; x = 5 PHI(7)-1 mod 7 = 55 mod 7 = 3.
3. Euclid's extended GCD algorithm
   1. GCD(4, 6): remainder of 4 into 6 is 2; remainder of 2 into 4 is 0; GCD is 2
   2. GCD(14, 22): remainder of 14 into 22 is 8; remainder of 8 into 14 is 6; remainder of 6 into 8 is 2; remainder of 2 into 6 is 0; GCD is 2
   3. Extend: find x, y s.t. xa + yn = gcd(a, n) as then if GCD is 1, xa + yn = 1 and x solves ax mod n = 1.
   4. Ex. 1: a = 5, n = 7
      g₀ = 7, x₀ = 0, y₀ = 1 (note g₀ = 5x₀ + 7y₀);
      g₁ = 5, x₁ = 1, y₁ = 0 (note g₁ = 5x₁ + 7y₁); q = g₀/g₁ = 1
      g₂ = 2 = 7 - 5q; x₂ = 0 - 1q = -1; y₂ = 1 - 0q = 1 (note g₂ = 5x₂ + 7y₂); q = g₁/g₂ = 2;
      g₃ = 1 = 5 - 2q; x₃ = 1 - (-1)2 = 3; y₃ = 0 - (1)2 = -2 (note g₃ = 5x₃ + 7y₃); q = g₂/g₃ = 0
      GCD is x₃, or 3.
   5. Hence 5x mod 7 = 1 => x = 3, and 5(3) + 7(-2) = 15 - 14 = 1
4. ax mod n = b
   1. Solve ax₀ mod n = 1, then x = bx₀ mod n
   2. Ex: 5x mod 7 = 3; as x₀ = 3, x = 3(3) mod 7 = 2
5. Chinese Remainder Theorem
   1. Let g = gcd(a, n) and g divide b. Then ax mod n = b has g solutions of the form
      x = [(b/g)x₀ + t(n/g)] mod n,
      where x₀ solves (a/g)x mod (n/g) = 1.
   2. Ex: solve 5x mod 21 = 1. 21 = 3(7); need x₁, x₂ such that
      5x₁ mod 3 = 1 and 5x₂ mod 7 = 1; solns. x₁ = 2, x₂ = 3. So the solution to x mod 3 = 2 and x mod 7 = 3 also solves 5x mod 21 = 1
      Technique: find y₁: (21/3)y₁ mod 3 = 1, so 7y₁ mod 3 = 1, or y₁ = 1
      find y₂: (21/7)y₂ mod 7 = 1, so 3y₂ mod 7 = 1, or y₂ = 5
      x = [(21/3)y₁x₁ + (21/7)y₂x₂] mod 21 = ((7)(1)(2) = (3)(5)(3)) mod 21 = 59 mod 21 = 17
6. Transposition ciphers
   1. Show rail-fence cipher as example
   2. Show anagramming