Category Archives: Number theory

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

March 1, 2009, 4:40 pm

Keeping things in context

Part of Article 131 in the first edition (1801...
Image via Wikipedia

I’ve started reading through Stewart and Tall’s book on algebraic number theory, partly to give myself some fodder for learning Sage and partly because it’s an area of math I’d like to explore. I’m discovering a lot about algebra in the process that I should have known already. For example, I didn’t know until reading this book that the Gaussian integers were invented to study quadratic reciprocity. For me, the Gaussian integers were always just this abstract construction that  Gauss invented evidently for his own amusement (which maybe isn’t too far off from the truth) and which exists primarily so that I would have something to do in abstract algebra class. Here are the Gaussian integers! Now, go and find which ones are units, whether this is a principal ideal domain, and so on. Isn’t this fun?

Well, yes, actually it is fun for me, but that’s because I like a…

Read More