Previous
Next

Columnar transpositions: Looking at the initial cycle

December 12, 2011, 7:45 am

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, cycles are an important concept for us. The question we’d like to think about is: Can we determine the disjoint cycle decomposition of a CTC just by knowing the number of columns used and the length of the plaintext? If so, then we have a very simple way of telling the order of a CTC: just find the lengths of all the cycles in its factorization and calculate the LCM. If not, then we’d like to know what information is necessary to do so — or if it is even possible.

To help with this investigation, I wrote a small program called ctc_cycles.m to do the calculations. You can get it here. This is a MATLAB program, but it runs perfectly well in GNU Octave if you don’t have MATLAB. I also have an older Java version that is not as nice. (I have a personal goal for next semester to learn enough Python to port it there.) The program uses the function introduced in this post to find and list all the cycles using a brute-force method. The program uses the complicated version of the formula which does not assume the number of columns divides the length of the plaintext. So, for instance, we can analyze \(\pi_{4, 27} \):

As you can see, the program lists the cycles, giving their contents and their length one by one. Here, we see that \(\pi_{4, 27} \) factors into two 9-cycles, two 3-cycles, and two 1-cycles. We don’t list the 1-cycles but we do note that 9 and 18 are fixed under this permutation.

Is it coincidental that we are using 4 columns, and the last two elements of the first 9-cycle are 16 and 4? Or that we are using a message of length \(27 = 3^3\), and the cycle lengths are all powers of 3? Well, the last bit does seem coincidental if you look at \(\pi_{5, 27} \):

 

Oh well. But notice the last two entries of that first cycle: 5, 25. And the fact that each cycle begins with the next consecutive positive integer. And the fact that the last entry in each cycle is 5 times the first entry. There are some patterns here worth exploring.

To get started, let’s look at the simplest case of a CTC: the one where \(C = 2\). As discussed in the first post in this series, this is called the “rail fence cipher” (RFC for short henceforward). Let’s take a look at \(\pi_{2,11}\), the permutation for the RFC used on a message of length 11. The calculations show that this is just one long 10-cycle:

$$\pi_{2,11} = (1, 6, 3, 7, 9, 10, 5, 8, 4, 2 )$$

(Remember \(0\) is always fixed in any CTC.) The thing you might notice here is the last three entries: 8, 4, 2, all of which are powers of 2. In another example, \(\pi_{2, 17}\), the permutation factors into two 8-cycles:

$$\pi_{2,17} = (1, 9, 13, 15, 16, 8, 4, 2)(3, 10, 5, 11, 14, 7, 12, 6)$$

And again, we get that descending sequence of powers of 2 in one of the cycles. In both cases, that descending sequence happened in the cycle that contains \(1\). Let’s call that cycle the initial cycle of the permutation.

Does the initial cycle of the RFC permutation always end in a descending sequence of powers of 2? Let’s investigate by starting with an extreme case — the case where the length of the message itself is a power of 2, say \(L = 2^k\) for some natural number \(k\). Recall that the formula for the RFC says that:

$$\pi_{2,L}(n) = \left\{ \begin{array}{ll}
\frac{n}{2} & \textrm{if} \ n \ \textrm{even} \\
\frac{n+L-1}{2} & \textrm{if} \ n \ \textrm{odd}
\end{array}
\right.$$

What does 1 map to under the RFC? According to the formula, that would be

$$\pi_{2, 2^k}(1) = \frac{1 + 2^k – 1}{2} = 2^{k-1}.$$

So the first two entries of the initial cycle are 1 and \(2^{k-1}\). What’s the third? Note that \(2^{k-1}\) is even, so the third entry would be calculated using the first piece of the formula:

$$\pi_{2, 2^k}(2^{k-1}) = \frac{2^{k-1}}{2} = 2^{k-2}.$$

Likewise, the fourth entry would be \(2^{k-2}\), the fifth entry would be \(2^{k-3}\), and so on until we make it down to \(16, 8, 4, 2\). Then \(\pi_{2, 2^k}(2) = 2/2 = 1\), and we complete the cycle. This proves that:

If \(L = 2^k\), then the initial cycle of \(\pi_{2, L}\) is \(1, 2^{k-1}, 2^{k-2}, \dots, 8, 4, 2)\).

Notice, too, that this result also holds if \(L = 2^k – 1\). If \(L\) is even, then the last character in the plaintext is always fixed; that character is always in position \(L-1\), and if \(L\) is even, then \(L-1\) is odd and hence \(\pi_{2,L}(L-1) = \frac{L-1 + L – 1}{2} = L-1\). Therefore the initial cycle is the same for both \(L = 2^k\) (which is even) and \(L = 2^k – 1\).

So what happens if \(L\) is not a power of 2? We saw an example of that above with \(\pi_{2, 11}\). This permutation was a single 10-cycle, \((1, 6, 3, 7, 9, 10, 5, 8, 4, 2 )\). We see that descending sequence 8, 4, 2 and would love to have a 16 in front of all that. We don’t get this — there’s a 5 there. Too bad! But notice: \( 16 \equiv 5 \textrm{mod} \, 11\). So we don’t get the 16 where we want it, but we do have 16 modulo the length of the message. Likewise, notice that \(32 \equiv 10 \, \textrm{mod} \, 11\). And \(64 \equiv 9 \, \textrm{mod} \, 11\). In fact, we see that the initial cycle is:

$$(1, 512 \, \textrm{mod} \, 11, 256 \, \textrm{mod} \, 11, 128 \, \textrm{mod} 11, \dots, 16 \, \textrm{mod} 11, 8, 4, 2)$$

Coincidence? We think not:

Theorem: If \(\lambda\) is the length of the initial cycle of \(\pi_{2,L}\), then the initial cycle itself is \((1, 2^{\lambda -1} \textrm{mod} \, L, 2^{\lambda -2} \textrm{mod} \, L , \dots, 8, 4, 2 )\).

We’ll save the proof of this for next time, because it gets technical and contains important items we need for other stuff. But we’ll end here by noting that a corollary to this theorem is that the length of the initial cycle has to be greater than \(\log_2 L\). Having a lower bound on this initial cycle length is a good thing, because it turns out the initial cycle is pretty important for questions involving the order of the RFC.

Top image: http://www.flickr.com/photos/bernatcg/

This entry was posted in Abstract algebra, Crypto, CTCs, Math, Math Monday, Number theory and tagged , , , , , . Bookmark the permalink.