Category Archives: Crypto

January 16, 2012, 8:00 am

So you want to learn to program?

To follow up on my last post about the importance of programming for everyone, I’m making a personal commitment to get my own coding skills up to “halfway-decent” level in 2012. The more I teach with Conrad Wolfram’s TED talk in the back of my mind, and the more I dig into computational geometry as a new research area, the more I see the need to be able to write good code. I’ve tried this before as a sort of lone ranger, sitting down with a terminal window and an O’Reilly book in front of me, with the intent of working through the book, but I never stuck with it. Fortunately, there are more good resources out there than ever to help:

  • There’s CodeYear and Codecademy. Codecademy provides simple, self-guided lessons on programming. Currently there are a number of lessons on Javascript, and there are more lessons in more languages on the way. CodeYear is a layer on top of Codecademy…

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

October 10, 2011, 10:53 am

What is a columnar transposition cipher?

http://www.flickr.com/photos/maistora/

We all have secrets to keep. Those secrets could be personal dirt we want to keep from others, or they could be something as mundane as our credit card numbers or medical histories. But all of us have information that we want to keep to ourselves or at least to a small circle of people whom we select. This is why the field of cryptology — the science of making and breaking coded messages, or more generally the notion of communicating in a secure way — is a viable and extremely active field of study these days.

I’ve been interested in cryptology ever since a student came to me in 1999 and asked me to direct an independent study on the subject for her. I’ve since taught topics courses in cryptology to math majors and to liberal arts students, and it always…

Read More

September 19, 2011, 8:00 am

Math Monday: What is casting out nines?

http://www.flickr.com/photos/artnoose/

Last week in this post, I asked for requests for math topics you’d like to read about. One person wrote in and asked:

Why don’t you enlighten us about the name “Casting Out Nines?” I learned a system in grade school with the same name –it was a way of checking multiplication and long division answers. Long before calculators.

A review please?

OK then. Casting out nines is an old-fashioned method of checking for errors in basic arithmetic problems (addition and subtraction too, not just multiplication and division). Here’s how it works, using addition as an example.

Let’s suppose I’m trying to add 32189 to 87011. I get a sum of 119200. But did I make a mistake? Do the following to check:

  1. Take the first number, 32189, and remove — “cast out” — any 9′s…

Read More

January 4, 2011, 8:41 pm

Bound for New Orleans

Happy New Year, everyone. The blogging was light due to a nice holiday break with the family. Now we’re all back home… and I’m taking off again. This time, I’m headed to the Joint Mathematics Meetings in New Orleans from January 5 through January 8. I tend to do more with my Twitter account during conferences than I do with the blog, but hopefully I can give you some reporting along with some of the processing I usually do following good conference talks (and even some of the bad ones).

I’m giving two talks while in New Orleans:

  • On Thursday at 3:55, I’m speaking on “A Brief Fly-Through of Cryptology for First-Semester Students using Active Learning and Common Technology” in the MAA Session on Cryptology for Undergraduates. That’s in the Great Ballroom E, 5th Floor Sheraton in case you’re there and want to come. This talk is about a 5-day minicourse I do as a guest lecturer in our…

Read More

November 11, 2008, 3:08 pm

Links for Tuesday

  • What’s that smell? It could be the latest in biometrics.
  • At Slashdot, a discussion on combining computer science and philosophy. I think that, in general, there is a lot of really interesting yet uncharted territory in the liberal arts arising from combining computing with [fill in humanities subject here].
  • Circuit City hits Chapter 11. The only reason I’m sorry to hear about this is because I know people who work for Circuit City who might lose their jobs. But that’s the only reason. There used to be a time, when I was a teenager, when going to Circuit City to paw over all the tech stuff was fun and exciting. Now when I go, it’s a game of “dodge the irritating service rep”.
  • Some nice tips on getting the most out of Google Scholar. Especially useful if, like me, you’re in a place that doesn’t have access to a lot of technical journals.
  • Mike at Walking Randomly is finding symbolic…

Read More

September 17, 2008, 11:56 am

It's official: They're prime

The numbers believed to be the 45th and 46th Mersenne primes have been proven to be prime. The 45th Mersenne prime is \(2^{37156667} -1\) and the 46th is \(2^{43112609} – 1\).Full text of these numbers is here and here.

Of course what you are really wanting to know is how my spreadsheet models worked out for predicting the number of digits in these primes. First, the data:

  • Number of digits actually in \(M_{45}\): 11,185,272
  • Number of digits actually in \(M_{46}\): 12,978,189

My exponential model (\(d = 0.5867 e^{0.3897 n}\)) was, unsurprisingly, way off — predicting a digit count of over 24.2 million for \(M_{45}\) and over 35.8 million for \(M_{46}\). But the sixth-degree polynomial — printed on the scatterplot at the post linked to above — was… well, see for yourself:

  • Number of digits predicted by 6th-degree polynomial model for \(M_{45}\):…

Read More

August 28, 2008, 1:57 pm

Estimating the digits in a Mersenne prime — for dummies

At the end of this post, I made a totally naive guess that the recently discovered candidate to be the \(M_{45}\), the 45th Mersenne prime, would have 10.5 million digits. There was absolutely no systematic basis for that guess, but I did suggest having an office pool for the number of digits, so what I lack in mathematical sophistication is made up for by my instinct for good nerd party games. On the other hand, Isabel at God Plays Dice predicted 14.5 million digits based on a number theoretic argument. Since I am merely a wannabe number theorist, I can’t compete with that sort of thing. But I can make up a mean Excel spreadsheet, so I figured I’d do a little data plotting and see what happened.

If you make a plot of the number of digits in \(M_n\), the nth Mersenne prime, going all the way back to antiquity, here’s what you get:

The horizontal axis is n and the vertical…

Read More

April 5, 2008, 9:53 am

Spring break report

My busier-than-usual Spring Break is all but over with. Here’s a brief update.

The ICMC went off much better than it looked like it was going to. This was my first of a three-year stint as Student Activities Director for the Indiana section of the MAA, and while my predecessor was really great an answering my questions about how to organize the ICMC, he could only answer the questions I could think of, and the un-thought-of questions were starting to pile up at an exponential pace the week before the contest. But with the generous help of Mike Axtell, who — sadly — is leaving the Indiana section for a new position in Minnesota, all the logistics went off just fine and we had no major incidents. Kudos to the Purdue, Rose-Hulman, and Taylor teams who finished first, second, and third respectively.

That was last weekend. On Tuesday and Wednesday of this week I had a very nice time at

Read More

March 27, 2008, 4:21 pm

On tour and on break

I’ve got a pretty full next week ahead of me. On Friday I’ll be in South Bend at the Indiana MAA section meeting, where I’ll be in charge of administering the Indiana Collegiate Mathematics Competition (read: putting out fires and making copies and grading). On Tuesday and Wednesday, I’ll be in the Chicago area giving a couple of talks on digital signature algorithms and on cryptology in general at Benedictine University. Sunday and Monday I’ll be (somewhat frantically) getting those talks fine-tuned. Next week is also spring break for us, which means it’s spring break for my kids as well, which means I’m a stay-at-home dad for a little while — perhaps the most enjoyable task of all of the above.

So I’ll be blogging only intermittently until next Thursday or so, just so you’ll know. I’ll be more likely to Twitter, so that’s where you can find me online most likely.