Tag Archives: Cycles

December 12, 2011, 7:45 am

Columnar transpositions: Looking at the initial cycle

Welcome to Math Monday! Each Monday here at Casting Out Nines, we feature a mathematics-themed article. Today’s is a new installment in an ongoing virtual seminar on columnar transposition ciphers.

Let’s return to our ongoing look at the columnar transposition cipher. In the last article, we introduced the notion of cycles. A cycle can be thought of as a cluster of points which are moved around in a circular nature by a permutation. All permutations — including the permutation implemented by a columnar transposition cipher — break down into a product of disjoint cycles, and we can determine the order of a permutation (the smallest nonnegative power of the permutation that returns it to the identity) by finding the least common multiple of the lengths of the cycles in its disjoint cycle decomposition.

Since one of the main questions we are asking about CTC’s is about their order,…

Read More

November 28, 2011, 7:45 am

Cycles, and the cycle decomposition of a permutation

Last week’s installment on columnar transposition ciphers described a formula for the underlying permutation for a CTC. If we assume that the number of columns being used divides the length of the message, we get a nice, self-contained way of determining where the characters in the message go when enciphered. Now that we have the permutation fully specified, we’ll use it to learn a little about how the CTC permutation works — in particular, we’re going to learn about cycles in permutations and try to understand the cycle structure of a CTC.

First, what’s a cycle? Let’s go back to a simpler permutation to get the basic concept. Consider the bijective function \(p\) that maps the set \(\{0,1,2,3,4, 5\} \) onto itself by the rule
$$p(0) = 4 \quad p(1) = 5 \quad p(2) = 0 \quad p(3) = 3 \quad p(4) = 2 \quad p(5) = 1$$
If you look carefully at the numbers here, you’ll see that some of…

Read More