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