\documentstyle{report}
\begin{document} 
{\LARGE Equivocation } \newline  
8-bit integer
\[ H(x) = -\sum_{i=1}^{2^8} \frac{1}{2^8} \log \frac{1}{2^8} = \log 2^8 = 8 \]
If parity = 0
\[ H(x|bit\, 8\, is\, 0) = -\sum_{i=1}^{2^7} \frac{1}{2^7} \log \frac{1}{2^7} = \log 2^7 = 7 \]
{\LARGE Joint Probability / Uncertainty } \\[0.5cm]
\underline{Case 1}  \newline
X = die throw,            Y = coin toss  
\[p(X=3,Y=head) = p(Y=head) p(X=3|Y=head)   \]
As $p(X=3|Y=head) = p(X=3) $ because they are independent 
          \[ p(X=3,Y=head) = p(Y=head) p(X=3) = \frac{1}{12} \]  
\underline{Case 2}   \newline
Toss coin \newline
on head : 3-sided die \newline
on tail : 6-sided die 
   
\[ p(X=3,Y=head) = p(Y=head) p(X=3|Y=head) = \frac{1}{2} \times \frac{1}{3} = \frac{1}{6}  \] 
                               
\[ p(X=3,Y=tail) = p(Y=tail) p(X=3|Y=tail) = \frac{1}{2} \times \frac{1}{6} = \frac{1}{12}  \]
In case 1, X=3,Y=head  (independent)
 \[H(X|Y) = H(X) = \log 6  \]
In case 2, X=3,Y=head  (dependent)
 \[ H(X|Y) = \sum_{Y}^{} p(Y) \sum_{X}^{} p(X|Y) \log p(X|Y) \]
 \[        = p(Y=head) \sum_{X}^{} p(X|Y=head) \log p(X|Y=head) \]
 \[          + p(Y=tail) \sum_{X}^{} p(X|Y=tail) \log p(X|Y=tail) \]
 \[        = \frac{1}{2} \log 18 \]  
 $H(M|C) = H(M) and p(M|C) = p(M)$    define perfect security \newline
{\Large Key Equivocation} \\[1cm]
The uncertainty $H(K|C)$ in the key given some ciphertext \newline
 \underline{Case 1} \newline
 KHOOR ZRUOG as a Caesar cipher:   $\Rightarrow H(K|C) = 0$ (see handout) \newline
 \underline{Case 2} \newline
       J as a Caesar cipher:    $\Rightarrow H(K|C) = 1$ \newline
Formula : $ H(K|C) = - \sum_{C}^{} p(C) \sum_{K}^{} p(K|C) \log p(K|C) $ \\[0.5cm]
 In case 1,
$ p(C)=26^{-10}\,\,and\,\,p(K|C) = \left\{ \begin{array}{r@{\quad if \quad}l}
   0 & K\not=23 \\ 1 & K=23 \end{array} \right. $
\[ H(K|C) = \sum_{K}^{} p(K|C) \log p(K|C) = \sum_{i=1}^{26^{10}} 26^{-10} 0 = 0 \]
In case 2 
$ p(C)=26^{-1}   and     p(K|C) = \left\{ \begin{array}{r@{\quad if \quad}l}
0 & K\not=9,25 \\ \frac{1}{2} & K=9 \\ \frac{1}{2} & K=25 \end{array} \right. $ 
\[ H(K|C) = - \sum_{C}^{} p(C) \sum_{K}^{} p(K|C) \log p(K|C) \]        
\[        = \sum_{i=1}^{26} \frac{1}{26} ( \frac{1}{2} \log \frac{1}{2} + \frac{1}{2} \log \frac{1}{2} ) = - \log \frac{1}{2} = 1 \]        
{\LARGE Unicity Distance} \\[0.5cm]
Smallest length of text $N$ such that $H(K|C) \approx 0 $ 
\[ N = \frac{H(K)}{D} \Rightarrow H(K) - DN = 0 \]
This is impossible when \# of Keys = \# meaningful mesg \\
So: $H(K) = \log 2^{RN} = RN$ \\
RN - DN = 0 \\
rM = 0 where R is absolute rate and r is the actual rate \newline

Example:
$Caesar  H(K) = \log 26 = 4.7 $ so \\
$N = \frac{4.7}{3.2} \approx 1.5 $ \\[1cm]
{\Large Number Theory} \\[1cm]
5 = 12 mod 7 \\
$12 \equiv_{7} 5$ (Mathmatical notation)   \\
12 = 5 + 7k \\[0.5cm]
a mod n = b \newline
Principle of modular arithmetic: mod can be moved into multiplication
and addition \newline

Examples:
$ 7\times9$ mod 4  \\
= (7 mod 4) (9 mod 4) mod 4\\
= 3 \\[0.5cm]

$ 2^{20}$ mod 3 = $(2^{10})(2^{10})$ mod 3 \\
$=(2^5)(2^5)(2^5)(2^5) mod 3 $ \\
$=(2^2mod 3)(2^3mod 3)(2^2mod 3)(2^3mod 3)(2^2mod 3)(2^3mod 3)(2^2mod 3)(2^3mod 3)(2^2mod 3)(2^3mod 3) mod 3$ \\
$=[(1)(2)(1)(2)(1)(2)(1)(2)(1)(2)] mod 3$ \\
= 16 mod 3 = 1 \\[0.5cm]


Solve ax mod n = 1 for any a and n (if possible)

Consider 2x mod 5 = 1. 2xmod 5 generates a complete set of residues, as

\[ 2(0) mod 5 = 0 \]
\[ 2(1) mod 5 = 2 \]
\[ 2(2) mod 5 = 4 \]
\[ 2(3) mod 5 = 1 \]
\[ 2(4) mod 5 = 3 \]

(and so 2x mod 5 = 1 has a solution -- x = 3). But 2x mod 4 will not:

\[ 2(0) mod 4 = 0 \]
\[ 2(1) mod 4 = 2 \]
\[ 2(2) mod 4 = 0 \]
\[ 2(3) mod 4 = 2 \]

(and so 2x mod 4 = 1 does not have a solution.)

Solution requires gcd(a,n) = 1 $\Rightarrow$ a, x relatively prime.
$2x mod 5$ gives a complete set of residues. After removing the zero
get a reduced set of residues, which is the set for which $ax mod n = 1$
has a solution. Totient function $\phi$ is the number of elements in the
reduced set of residues. \newline

$\phi(4)=2 \\ \phi(5)=4 \\ \phi(p)=p-1$ when p is prime \newline

$15=3\times5     \phi(15)=8=2\times4=(3-1)(5-1) \\
\phi(pq)$ = pq-p-q+1 = (p-1)(q-1) when p and q is prime














\end{document}
