%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%
%
\documentclass[10pt]{article}
\usepackage[textheight=10in]{geometry}

\usepackage{verbatim}
\usepackage{amsmath}
\usepackage{amsfonts} % to get \mathbb letters

\usepackage[utf8]{inputenc}
\DeclareFixedFont{\ttb}{T1}{txtt}{bx}{n}{9} % for bold
\DeclareFixedFont{\ttm}{T1}{txtt}{m}{n}{9}  % for normal
% Defining colors
\usepackage{color}
\definecolor{deepblue}{rgb}{0,0,0.5}
\definecolor{deepred}{rgb}{0.6,0,0}
\definecolor{deepgreen}{rgb}{0,0.5,0}

\usepackage{listings}

%Python style from 
%http://tex.stackexchange.com/questions/199375/problem-with-listings-package-for-python-syntax-coloring
\newcommand\pythonstyle{\lstset{
  language=Python,
  backgroundcolor=\color{white}, %%%%%%%
  basicstyle=\ttm,
  otherkeywords={self},            
  keywordstyle=\ttb\color{deepblue},
  emph={MyClass,__init__},          
  emphstyle=\ttb\color{deepred},    
  stringstyle=\color{deepgreen},
  commentstyle=\color{red},  %%%%%%%%
  frame=tb,                         
  showstringspaces=false,
  numbers=left,numberstyle=\tiny,numbersep =5pt
}}
\usepackage{hyperref}

\begin{document}

\pythonstyle{}

\begin{center}
\Large{
Cryptanalysis \\
Ethan Bolker \\
Spring 2015
}
\end{center}

\section{Frequency tables}

First task is to build a character frequency table from a text file,
using a Python \lstinline!dictionary!. I found out about dictionaries
by googling \verb!python 3 dictionary! and reading
\url{docs.python.org/3/tutorial/datastructures.html}.

In \lstinline!frequencies0.py! all I do is test very elementary
dictionary code:

\lstinputlisting{frequencies0.py}

Output is what I expected:

\begin{verbatim}
myshell> python frequencies0.py 
{'x': 0.0, 'e': 0.12, 'a': 0.07}
x: 0.0
e: 0.12
a: 0.07
a: 0.07
e: 0.12
x: 0.0
\end{verbatim}

Now I'll borrow code I wrote for the \lstinline!echo! program to read
a file a line at time, then read that line a character at a time and
build the frequency table:

\lstinputlisting[firstnumber=9,firstline=9,lastline=17]{frequencies1.py}

The test code is

\lstinputlisting[firstnumber=25,firstline=25,lastline=28]{frequencies1.py}

Here's the output (shortened a little bit). The characters appear in
ascii order. I've counted punctuation marks, and treat upper and lower
case letters as different. In the next round I'll fix that. I'll also
sort by frequency, and test on a real text file, not a Python program.

\begin{verbatim}
myshell> python frequencies1.py frequencies1.py 

: 32
 : 167
": 2
#: 9
...
+: 3
-: 1
.: 5
0: 2
1: 4
...
8: 1
:: 8
=: 7
B: 1
E: 1
...
M: 2
P: 1
...
a: 35
b: 12
c: 18
d: 7
e: 56
...
v: 1
w: 2
x: 2
y: 14
{: 1
}: 1
\end{verbatim}

Strings in Python are sequences of 16 bit unicode characters. That's
something computer science students have to pay attention to. We can
afford to be naive. (If you're interested, look at
\url{www.diveintopython3.net/strings.html}.) Finding and using
the Python methods \lstinline!lower()! and \lstinline!isalpha()! was
easy. 

Here's the code:

\lstinputlisting[firstnumber=9,firstline=9,lastline=18]{frequencies2.py}

I tested the next version of my code on the first chapter of
\emph{Alice in Wonderland}, downloaded from project Gutenberg
(\url{www.gutenberg.org/files/11/11-h/11-h.htm#link2HCH0001}).

Sorting a dictionary on its values instead of its keys is much more
subtle. Stackoverflow to the rescue: there's an answer here upvoted
more than a thousand times:
\url{stackoverflow.com/questions/613183/sort-a-python-dictionary-by-value}.
The code there produces a list of tuples --- I printed it to see what
it looked like, and discovered the sorting was in reverse
order. Here's my final testing code:

\lstinputlisting[firstnumber=25,firstline=25,lastline=31]{frequencies2.py}

The output shows the letter frequencies begin \verb!etoahinsrld...! ---
not too far from \verb!etaoinshrdl...!. (Check out
\url{en.wikipedia.org/wiki/Etaoin_shrdlu}.)

\begin{verbatim}
python frequencies2.py alice.txt
[('z', 4), ('j', 6), ('q', 6), ('x', 7), ('v', 68), ('k', 96), ('p', 131), ('b', 141), ('m', 144), ('y', 163), ('c', 171), ('f', 186), ('g', 202), ('u', 249), ('w', 252), ('d', 387), ('l', 418), ('r', 453), ('s', 507), ('n', 558), ('i', 561), ('h', 592), ('a', 678), ('o', 695), ('t', 867), ('e', 1079)]
e: 1079
t: 867
o: 695
a: 678
h: 592
i: 561
n: 558
s: 507
r: 453
l: 418
d: 387
w: 252
u: 249
g: 202
f: 186
c: 171
y: 163
m: 144
b: 141
p: 131
k: 96
v: 68
x: 7
q: 6
j: 6
z: 4
\end{verbatim}

\section{Next steps}

\begin{itemize}

\item Convert counts to frequencies.

\item Build a table of digraph frequencies.

\item Choose a random permutation.

\item Encode plain text using a permutation.

\item Decide how best to compare two frequency tables for decoding
  purposes. Just the most frequent characters will be relevant.

\item Think about how to use frequency tables to decode. This will be
  partly automated and partly automatic, so the user interface is a
  little tricky.

  For messages where word boundaries are preserved, checking potential
  words against a real English dictionary will be useful
\end{itemize}

\newpage
\emph{
Here is the \LaTeX{} source for this document. You can cut it from the
pdf and use it to start your answers. I used the} \verb!\jobname! 
\emph{macro for the source file name, so you can call your file by any
  name you like.}
\verbatiminput{\jobname}

\end{document}