Breaking Caesar’s Cipher (part III)

In the last installment of this series, we looked at Markov chains as a mean of estimating the likelihood of a given piece of text of actually being a message, written in English, rather than mere gibberish.

This week, we finally piece everything together to obtain a program to crack Caesar’s cipher without (much) human intervention.

Breaking Caesar’s Cipher (Caesar’s Cipher, part II)

In the last installment of this series, we had a look at Caesar’s cipher, an absurdly simple encryption technique where the symmetric encryption only consists in shifting symbols places.

While it’s ridiculously easy to break the cipher, even with pen-and-paper techniques, we ended up, last time, surmising that we should be able to crack the cipher automatically, without human intervention, if only we had a reasonable language model. This week, let us have a look at how we could build a very simple language model that does just that.

Building a Tree from a List in Linear Time (II)

Quite a while ago, I proposed a linear time algorithm to construct trees from sorted lists. The algorithm relied on the segregation of data and internal nodes. This meant that for a list of data items, nodes were allocated (but only contained data; the others just contained pointers.

While segregating structure and data makes sense in some cases (say, the index resides in memory but the leaves/data reside on disk), I found the solution somewhat unsatisfactory (but not unacceptable). So I gave the problem a little more thinking and I arrived at an algorithm that produces a tree with optimal average depth, with data in every node, in linear time and using at most extra memory.

Caesar’s Cipher

Julius Caesar, presumably sometimes during the war in Gaul, according to Suetonius, used a simple cipher to ensure the privacy of his communications.

Caesar’s method can hardly be considered anything close to secure, but it’s still worthwhile to have a look at how you can implement it, and break it, mostly because it’s one of the simplest substitution ciphers.

A Special Case…

Expressions with floors and ceilings ( and ) are usually troublesome to work with. There are cases where you can essentially remove them by a change of variables.

Turns out, one form that regularly comes up in my calculations is , and it bugged me a while before I figured out the right way of getting rid of them (sometimes).

Compressed Series (Part II)

Last week we looked at an alternative series to compute , and this week we will have a look at the computation of . The usual series we learn in calculus textbook is given by

We can factorize the expression as

Compressed Series (Part I)

Numerical methods are generally rather hard to get right because of error propagation due to the limited precision of floats (or even doubles). This seems to be especially true with methods involving series, where a usually large number of ever diminishing terms must added to attain something that looks like convergence. Even fairly simple sequences such as

may be complex to evaluate. First, is cumbersome, and becomes small exceedingly rapidly.

Suggested Reading: Cryptography: The science of secret writing

Laurence Dwight Smith —Cryptography: The science of secret writing — Dover, 1943, 164 pp. ISBN 0-486-20247-X

(Buy at Amazon.com)

Damn you, Napier!

Briggs‘ logarithms (often mistakenly understood to be Napier‘s logarithms) is such an useful function that most of us don’t really think about it, until we have to. Everyone’s familiar with its properties:

(1)

but suddenly,

What can we do with this last one?

Stemming

A few weeks ago, I went to Québec Ouvert Hackathon 3.3, and I was most interested by Michael Mulley’s Open Parliament. One possible addition to the project is to use cross-referencing of entries based not only on the parliament-supplied subject tags but also on the content of the text itself.

One possibility is to learn embeddings on bags of words but on stemmed words to reduce the dimensionality of the one-hot vector, essentially a bitmap where the bit corresponding to a word is set to 1 if it appears in the bag of words. So, let us start at the beginning, stemming.