Lecture 5 Notes;  April 9, 1997; Notetaker: Christina Chang

Modular Arithmetic:

* solve ax mod n = 1 by the Extended Euclidean algorithm
	Note a*x + n*y = g at each step
e.g. to solve 5x mod 7 = 1: g=gcd(5,7); a = 5, n = 7
	g	x 	y	q	a*x + n*y
	7	0	1		5*0 + 7*1 = 7
	5	1	0	1	5*1 + 7*0 = 5
	2	-1	1	2	5*(-1)+7*1 = 2
	1	3	-2	2	5*3 + 7*(-2) = 1
	0
	so x = 3
* solve x in: ax mod n = b 
	if we can find x0 s.t. ax0 mod n = 1, then we have
 			a(x0b mod n) = b
	thus x = x0b is the solution


Cipher:
* transposition cipher: diffusion effect (suggested by Shannon)
  can be detected by frequency count (digram, trigram etc.)
* substitution cipher: confusion effect (suggested by Shannon)
	 simple substitution: one mapping applied to all components
	 	e.g. Caesar cipher
  Mathematically,
	 f(m)=(m+k) mod 26 where k is the key is an affine transformation: 
 	 f(m)=(km + k') mod n where gcd(k,n) = 1 can be attacked by comparing
		 the shift with frequency distribution of normal English text
	(example given in handout)
* homophonic substitution
	multiple mapping for each character/symbol