Category Archives: Weekly features

November 21, 2011, 7:45 am

A formula under the hood of a columnar transposition cipher

It’s been a couple of Math Mondays since we last looked at columnar transposition ciphers, so let’s jump back in. In the last post, we learned that CTC’s are really just permutations on the set of character positions in a message. That is, a CTC is a bijective function \( \{0, 1, 2, \dots, L-1\} \rightarrow \{0, 1, 2, \dots, L-1\}\) where \(L\) is the length of the message. One of the big questions we left hanging was whether there was a systematic way of specifying that function — for example, with a formula. The answer is YES, and in this post we’re going to develop that formula.

Before we start, let me just mention again that all of the following ideas are from my paper “The cycle structure and order of the rail fence cipher”, which was published in the journal Cryptologia. However, the formula you’re about to see here is a newer (and I think improved) version of the one in the…

Read More

November 7, 2011, 7:45 am

Math Monday: Columnar transposition ciphers and permutations, oh my

I hope you enjoyed Ed’s guest posts on NP-complete problems on TV the last couple of Mondays. It’s always great to hear from others on math that they are thinking about. This week it’s me again, and we’re going to get back to the notion of columnar transposition ciphers. In the first post about CTCs, we discussed what they are and in particular the rail fence cipher which is a CTC with two columns. This post is going to get into the math behind CTCs, and in doing so we’ll be able to work with CTCs on several different levels.

A CTC is just one of many transposition ciphers, which is one of the basic cryptographic primitives. Transposition ciphers work by shuffling the characters in the message according to some predefined rule. The way these ciphers work is easy to understand if we put a little structure on the situation.

First, label all the positions in the message from \(0\) to …

Read More

October 24, 2011, 7:30 am

Math Monday: TV Lawyers Solve NP-Complete Problem (part 2)

This is the second installment of a two-part article from guest blogger Ed Aboufadel. Thanks again, Ed, for contributing.

In Part I, we learned of an instance of the NP-complete problem subset-sum [1] that was solved by three lawyers on an episode of the USA Network show Suits [2]. The problem was to go through a set of deposits made to five banks in Liechtenstein and find a subset of deposits, where the total of the deposits was $152,375,242.18. Described as “simple mathematics” by one of the lawyers, the team solved the problem in a relatively short length of time. They couldn’t use a quick approximation algorithm for subset-sum, since they needed the sum to be exactly equal to their target amount. So, were they just lucky, smarter than the rest of us, or did they do something practically impossible?

Consider the following “back of the envelope” calculations. First,…

Read More

October 17, 2011, 7:30 am

Math Monday: TV Lawyers Solve NP-Complete Problem (part 1)

For the next couple of weeks, Math Monday here at the blog will feature a guest blogger. Ed Aboufadel is Professor of Mathematics and chair of the Mathematics Department at Grand Valley State University, where I work. He’ll be writing a two-part series on a neat appearance of an NP-complete problem on network TV, adding yet another data point that mathematics is indeed everywhere. Thanks in advance, Ed!

On the new USA-network TV series Suits [1], Harvey Specter is a senior partner at the law firm of Pearson Hardman, and Mike Ross is his new associate. Mike never went to law school, but he combines a photographic, elephantine memory with near-genius intelligence to fake it well. Harvey is in on the deception, but none of the other partners know. During the eighth episode of the first season of Suits (broadcast August 11, 2011), Harvey and Mike, working with Louis Litt, a…

Read More

September 28, 2011, 4:00 am

Midweek recap, 09.28.2011

Good stuff from the internet this past week:

Read More

September 21, 2011, 9:00 am

Midweek recap, 9.21.2011

Interesting stuff from elsewhere on the web this week:

Read More

August 26, 2011, 9:00 am

Friday Random 10, 8/26/11

Don’t look now, but it’s the return of the Friday Random 10. Ten songs selected at random from my family’s, um, eclectic iTunes library. Notice how I say “my family’s” library, so as to deflect questions about why there are so many kids’ songs or Glee stuff coming up.

  1. Candles (Glee cast version); Glee: The Music Presents the Warblers
  2. Spiritual; Johnny Cash, Unchained
  3. BWV Praeludium et Fuga in A; James Kibbie, Bach Organ Works: Preludes and Fugues
  4. Sara; Fleetwood Mac, Greatest Hits
  5. It Doesn’t Matter; Alison Krauss & Union Station, So Long So Wrong
  6. Celebration; Kool & the Gang, Gold
  7. Amazed; Lonestar, Lonely Grill
  8. All the Way My Savior Leads Me; Rich Mullins, The World as Best I Remember It, vol. 2
  9. Soul Refreshing; Robert Randolph & The Family Band, Unclassified
  10. Jealous Hearted Man; Muddy Waters, Hard Again
Let’s focus this week on James Kibbie, a master organist a…

Read More

November 12, 2010, 4:04 pm

This week in screencasting: Optimization-palooza

My calculus class hit optimization problems this week — or it might be better to say the class got hit by optimization problems. These are tough problems because of all their many moving parts, especially the fact that one of those parts is to build the model you plan to optimize. Most of my students have had calculus in high school, but too many calculus courses in high school as well as college focus almost primarily on algorithms for computation and spend little to no time with how to create a model in the first place. Classes that are so structured are doing massive harm to students in a number of ways, but that’s for another post or two.

Careful study of worked-out examples is an essential part of understanding optimization problems (though not the only part, and this alone isn’t sufficient). The textbook has a few of these. The professor can provide more, but class time really …

Read More

October 15, 2010, 9:00 am

Friday random 10

Here’s some music for the end of the week, straight off the iPhone set to random shuffle:

  1. Daughters (John Mayer, Heavier Things)
  2. Custard Pie (Led Zeppelin, Physical Graffiti)
  3. Far East Medley (Bela Fleck and the Flecktones, Live Art)
  4. Heartbreak Hotel (Elvis Presley, Elvis 30 #1 Hits)
  5. On Your Shore (Enya, Watermark)
  6. Treasure of the Broken Land (Mark Heard, High Noon)
  7. When It’s Good (Ben Harper, Diamonds on the Inside)
  8. You Send Me (Steve Miller Band, Fly Like an Eagle)
  9. When Love Comes Around (Alan Jackson, Drive)
  10. Big Things Too (Veggie Tales, Veggie Tunes 2)

I have to focus this time on the first one in the list, John Mayer’s “Daughters”. People have many different opinions about John Mayer, not all of them good, but I’m a big fan — and mainly because of this song. Mayer has a sort of reputation as a womanizer but his insights on girls and parenting in this song…

Read More

July 30, 2010, 8:00 am

The return of Friday Random 10

Friday Random 10 has slipped out of the rotation lately, so let’s fix that. Hitting the random shuffle button on the iPhone, we have…

  1. Delia’s Gone (Johnny Cash, American Recordings)
  2. Guide Vocal (Genesis, Duke)
  3. All Your Love (Otis Rush, Essential Chicago Blues)
  4. Why Should I Feel Lonely (Robert Randolph & the Family Band, Unclassified)
  5. Catch Me If I Try (David Wilcox, East Asheville Hardware)
  6. House of Tom Bombadil (Nickel Creek, Nickel Creek)
  7. Digital Man (Rush, Signals)
  8. Fei Hua Dian Cui (Lui Pui-Yuen, China: Music of the Pipa)
  9. Turn the Page (Rush, Hold Your Fire)
  10. A Little Bluer Than That (Alan Jackson, Drive)

Here’s the video for “Delia’s Gone” (#1 on the list). The song is a classic “death ballad”, one of the standard idioms of country and folk music. And yet, when it came out in 1994, none of the country music stations on radio or TV wanted to play it because…

Read More