4 <title>Breaking transposition ciphers
</title>
5 <meta http-equiv=
"Content-Type" content=
"text/html; charset=UTF-8"/>
6 <style type=
"text/css">
15 h1 { font-size:
3em; }
16 h2 { font-size:
2em; }
17 h3 { font-size:
1.6em; }
19 text-decoration: none;
22 -moz-border-radius:
5px;
23 -web-border-radius:
5px;
31 text-shadow:
0 0 20px #
333;
37 text-shadow:
0 0 20px #
333;
46 <textarea id=
"source">
48 # Breaking transposition ciphers
50 attack the fort at dawn
59 Generally quite familiar...
61 ## Try all the keys, pick the one that looks most like Englilsh
65 # ...Pick one that looks most like English
67 But the naïve Bayes score will always be the same!
69 * Same letters, just a different order.
71 Score by probability of substrings of letters
73 * Bigrams, trigrams, _n_-grams
79 Given `count_2l.txt` and `count_3l.txt`, counts of bigrams and trigrams in English
81 # Write a function that returns all the _n_-grams for a text, given _n_
82 * Assume the text is already sanitised
84 # Build `P2l`, `P3l` (after `Pl`), `Pbigrams`, `Ptrigrams` (after `Pletters`)
90 What are the possible keys?
98 What's the transposition of 'cat'?
108 # Equivalence classes and canonical forms
110 Lots of words yield the same transposition
112 * They're all in the same equivalence class
113 * Only need to test one from the class
115 General idea: if there are different ways to represent something, pick one to make comparisons easier
117 * Canonical form, canonical representation
121 # Finding the transpositions to try
125 if it's a new transposition:
129 What data structure to use to store the transpositions?
133 <script src=
"http://gnab.github.io/remark/downloads/remark-0.6.0.min.js" type=
"text/javascript">
136 <script type=
"text/javascript"
137 src=
"http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML&delayStartupUntil=configured"></script>
139 <script type=
"text/javascript">
140 var slideshow = remark.create({ ratio:
"16:9" });
145 skipTags: ['script', 'noscript', 'style', 'textarea', 'pre']
148 MathJax.Hub.Queue(function() {
149 $(MathJax.Hub.getAllJax()).map(function(index, elem) {
150 return(elem.SourceElement());
151 }).parent().addClass('has-jax');
153 MathJax.Hub.Configured();