- Greetings and Felicitations
- For NTU: All homework is due 1 week after the due date; I'll put this explicitly on future assignments

- Solving
*ax*mod*n*= 1:- {
*r*_{1}, ...,*r*_{PHI(n)}} reduced set of residues - by definition, {
*ar*_{1}mod*n*, ...,*ar*_{PHI(n)}mod*n*} is same set - So, PI(
*ar*mod_{i}*n*) = PI*r*(product from 1 to PHI(_{i}*n*)) - This means (
*a*^{PHI(n)}mod*n*) PI*r*= PI_{i}*r*, giving_{i}*a*^{PHI(n)}mod*n*= 1. - Ex:
*a*= 5,*n*= 7; 5*x*mod 7 = 1;*x*= 5 PHI(7)-1 mod 7 = 55 mod 7 = 3.

- {
- Euclid's extended GCD algorithm
- GCD(4, 6): remainder of 4 into 6 is 2; remainder of 2 into 4 is 0; GCD is 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
- 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. - Ex. 1:
*a*= 5,*n*= 7

*g*_{0}= 7,*x*_{0}= 0,*y*_{0}= 1 (note*g*_{0}= 5*x*_{0}+ 7*y*_{0});

*g*_{1}= 5,*x*_{1}= 1,*y*_{1}= 0 (note*g*_{1}= 5*x*_{1}+ 7*y*_{1}); q =*g*_{0}/*g*_{1}= 1

*g*_{2}= 2 = 7 - 5*q*;*x*_{2}= 0 - 1*q*= -1;*y*_{2}= 1 - 0*q*= 1 (note*g*_{2}= 5*x*_{2}+ 7*y*_{2});*q*=*g*_{1}/*g*_{2}= 2;

*g*_{3}= 1 = 5 - 2*q*;*x*_{3}= 1 - (-1)2 = 3;*y*_{3}= 0 - (1)2 = -2 (note*g*_{3}= 5*x*_{3}+ 7*y*_{3});*q*=*g*_{2}/*g*_{3}= 0

GCD is*x*_{3}, or 3. - Hence 5
*x*mod 7 = 1 =>*x*= 3, and 5(3) + 7(-2) = 15 - 14 = 1

*ax*mod*n*=*b*- Solve
*ax*_{0}mod*n*= 1, then*x*=*bx*_{0}mod*n* - Ex: 5
*x*mod 7 = 3; as*x*_{0}= 3,*x*= 3(3) mod 7 = 2

- Solve
- Chinese Remainder Theorem
- Let
*g*= gcd(*a*,*n*) and*g*divide*b*. Then*ax*mod*n*=*b*has*g*solutions of the form

*x*= [(*b*/*g*)*x*_{0}+*t*(*n*/*g*)] mod*n*,

where*x*_{0}solves (*a*/*g*)*x*mod (*n*/*g*) = 1. - Ex: solve 5
*x*mod 21 = 1. 21 = 3(7); need*x*_{1},*x*_{2}such that

5*x*_{1}mod 3 = 1 and 5*x*_{2}mod 7 = 1; solns.*x*_{1}= 2,*x*_{2}= 3. So the solution to*x*mod 3 = 2 and*x*mod 7 = 3 also solves 5*x*mod 21 = 1

Technique: find*y*_{1}: (21/3)*y*_{1}mod 3 = 1, so 7*y*_{1}mod 3 = 1, or*y*_{1}= 1

find*y*_{2}: (21/7)*y*_{2}mod 7 = 1, so 3*y*_{2}mod 7 = 1, or*y*_{2}= 5

*x*= [(21/3)*y*_{1}*x*_{1}+ (21/7)*y*_{2}*x*_{2}] mod 21 = ((7)(1)(2) = (3)(5)(3)) mod 21 = 59 mod 21 = 17

- Let
- Transposition ciphers
- Show rail-fence cipher as example
- Show anagramming

You can get this document in Postscript, ASCII text, or Framemaker version 5.1.

Notes by Christina Chang: [Postscript] [Text] [Microsoft Word]

Send email to cs253@csif.cs.ucdavis.edu.

Department of Computer Science

University of California at Davis

Davis, CA 95616-8562