Category Archives: Crypto

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 Introduction to the Mathematical Sciences activity course for freshmen.
  • On Friday at 11:20, I’m giving a talk called “Inverting the Linear Algebra Classroom” in the MAA Session on Innovative and Effective Ways to Teach Linear Algebra. Thats in Rhythms I, 2nd floor Sheraton. This talk is an outgrowth of this blog post I did back in the spring following the first non-MATLAB attempt at the inverted classroom approach I did and will touch on the inverted classroom model in general and how it can play out in Linear Algebra in particular.

Both sessions I’m speaking in are loaded with what look to be excellent talks, so I’m excited about participating. I’d be remiss if I didn’t mention that Gil Strang and David Lay are two of the organizers of the linear algebra setting, which is like a council of the linear algebra gods.

I’ll give Casting Out Nines readers a sneak peek at my two talks by telling you I’ve set up a web site that has the Prezis for both talks along with links to the materials I mention in the talks. And if you’re there in New Orleans, come by my talks if you have the slots free or just give me a ring on my Twitter and I’d love to meet up with you.

Comments Off on Bound for New Orleans

Filed under Blog announcements, Crypto, Inverted classroom, Linear algebra, Math, Peer instruction, Teaching

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 integrals that the new version of MATLAB can’t do. This is a really important series he’s doing, and his articles are a great resource for MATLAB users.
  • Speaking of math, here’s Carnival of Mathematics #43.
  • The University of Cincinnati is trying out a market-based approach to its various schools that might levy budget cuts on programs that don’t produce. What a concept! Of course the anti-free market people are running wild in the comments.
  • Finally, make sure you thank an engineer today.

1 Comment

Filed under Crypto, Engineering, Higher ed, Math, Technology

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}: 11,819,349
  • Number of digits predicted by 6th-degree polynomial model for M_{46}: 13,056,236

So my model was off by 634,077 digits — about 6% error — for M_{45}. But the difference was only  78,047 digits for M_{46}, which is only about 0.6% error. That’s not too bad, if you asked me.

There’s only one piece of bad news that prevents me from publishing this amazing digit-count predicting device, and you can spot it in the graph of the model:

So evidently the number of digits in M_{n} will max out around M_{49} and then the digit count will begin to decrease, until somebody discovers M_{55}, which will actually have no digits whatsoever. Um… no.

1 Comment

Filed under Crypto, Geekhood, Math

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 axis is the number of digits in M_n.

Admit it — one look at this plot and you’re itching to add some trendlines. Here’s what you get when you add both an exponential trendline (perhaps the obvious choice given the shape) and a 6th-degree polynomial:

The exponential one has a higher R^2 value, but that’s perhaps misleading because of the really good fit for all those low-digit Mersenne primes that happened prior to around M_{30}. We’ll take that issue up in a moment. But for now, let’s put those trendline equations to work. The exponential trendline would predict that M_{45} would have a digit count of

0.5867 e^{0.3897 \times 45} = 0.5867 e^{17.5365} \approx 24,233,786

which is obviously rather a lot more than either my prediction or Isabel’s; and if you put in x=45 into the 6th-degree polynomial, you get a digit count of 11819349, which is in the ballpark of both my rough estimate and Isabel’s estimate.

It doesn’t make much sense, though, to include all Mersenne primes, since Mersenne primes didn’t even cross the 100-digit mark until M_{13} in 1952. A more accurate idea — if you can call this kind of reasoning accurate in the first place — would be to run the numbers starting at around M_{20} and seeing what we get. I’ll save that for later, unless somebody wants to beat me to it.

5 Comments

Filed under Crypto, Geekhood, Math

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 Benedictine University near Chicago as the guest speaker to the Math Club and to Manu Kaur‘s topics course in cryptology. I gave a talk to the Math Club on cryptology in general — 50 minutes to cover the whole subject! — and despite some technical difficulties, the talk went reasonably well. There were close to 75-80 people in the audience! Then, the next day, I gave a talk on the Digital Signature Algorithm to the crypto class. In between, I got the rare opportunity to talk shop with Prof. Kaur on cryptography, and I also got a very nice tour of nearby Naperville, which is really quite lovely. (Not what I expected for Chicagoland suburbia.)

Benedictine has a fine department, and I was especially impressed by their students. To have close to 80 students show up in the middle of the day for a Math Club ta,lk at a school of under 3,000 students, is really amazing, and I got some very good questions after the talk. Following the digital signatures talk, one student asked me a really insightful question about Blowfish and SSL encryption; not only was this an undergrad asking the question, he was an undergrad chemistry major. And everywhere you looked, students were working on things — the science labs in particular seemed to be full every moment I was there.

St. Procopius AbbeySpecial treat for me: I got to spend the night in the extraordinary St. Procopius Abbey amongst the Benedictine monks. I’ve been reading Thomas Merton and the like for a long time, and the monastic life has been a guiding force in my Christian experience ever since I became a Christian, but until this week I had never actually gotten to experience monastic life firsthand. The abbey itself is breathtaking, with its Edward Dart-designed architecture combining soaring vertical spaces with hidden rooms for prayer and meditation, with a common thread of simplicity and silence throughout. I’m considering making a longer retreat there sometime soon. Something about the kindness, simplicity, and warmth of the abbey and the monks who live there follows one home from a place like this, and I could certainly use more of that.

So I’m wrapping up break doing the stay-at-home dad thing, having stayed with the girls for the last couple of days and spending the weekend doing the same before getting back to work on Monday. Ironically, this semester I made the conscious choice at the beginning not to emphasize scholarship so much but focus almost all my energies on teaching, but I ended up with one of the busiest semesters I’ve had scholarship-wise in a long time, mostly stuff that I have done or wrapped up this week! Now to finish off those pesky last five weeks of the semester.

2 Comments

Filed under Christianity, Crypto, Higher ed, Life in academia, Math, Personal, Student culture, Vocation

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.

2 Comments

Filed under Blog announcements, Crypto

Happy Birthday, William Friedman

Today is the birthday of William Friedman, one of the fathers of modern cryptology and an unsung American hero from World War II.

Before Friedman, cryptology could be described at best as a hodgepodge of tricks and unproven methods for securing information. Some tricks worked better than others. But there was no math in cryptology to quantify the strength (and exploit the weaknesses) of ciphers, really, until Friedman came along and brought the power of modern statistical techniques to bear on such problems as breaking rotor-machine ciphers. He almost single-handedly broke the Japanese PURPLE cipher, and in what’s surely one of the greatest problem-solving feats of all time, his team was able to complete reconstruct a PURPLE cipher machine using only plaintext and ciphertext samples — no technical diagrams were used.

He later suffered a major nervous breakdown, blamed mostly on his intense work on the PURPLE problem. I don’t think most human beings would have lasted even as long has he did and would have gone much further over the edge.

Here’s a page on Friedman at the National Security Agency web site. And here’s the Wikipedia article on Friedman. He’s a fascinating figure in both math history and American history, and more people should know about him.

Comments Off on Happy Birthday, William Friedman

Filed under Crypto, Math

Perhaps my favorite final exam problem ever.

Check out problem 5 on the final exam I am giving today in my Cryptology topics class.

Cartoon-Final-1

Thanks, XKCD.

Technorati Tags: ,

Comments Off on Perhaps my favorite final exam problem ever.

Filed under Crypto, Geekhood, Teaching

PlayStations as distributed computing nodes

This is cool:

Stanford University’s Folding@Home project, which puts personal computers to work studying the complicated process of protein folding, could soon get a big boost from an unlikely direction. Starting this month, owners of Sony’s PlayStation 3 video-game console will be able to take part in the research project when they’re not busy playing games.

Researchers have recruited about 200,000 desktop machines to participate in the project, which has implications for medical science. But the officials are bullish about PlayStations, according to Scientific American, because the gaming devices actually perform some simulations faster than most computers.

Here’s the whole Scientific American story. And there’s lots more distributed computing projects where that came from, such as Project RC5 which our Mac mini at home crunches on all day and night.

[via Wired Campus Blog]

Technorati Tags: , ,

1 Comment

Filed under Crypto, Software, Technology

Fall Break overview

Fall Break is upon us, as is fall itself with rainy, cool weather today. It’s a break, but a full one:

  • This is the first day in over six weeks that I have had substantive time to work on the dual-degree engineering program. The deadline for curriculum proposals is coming up shortly and the thing needs to get done. I think I’ll make it. Some tweaking needs to be done: since we offer Calculus III only once every two years, students who want to do engineering but who start the program in even-numbered years can’t take it until they are juniors, which puts them a year behind in the engineering program. I’ve got a workaround right now for that, but it’s not pretty. So I am lobbying my department and dean to have Calculus III offered every year, like a normal math department would do.
  • This semester has been kicking my rear since about day 3 and hasn’t stopped. I have 14 hours’ of teaching plus being on P&T, which is about the equivalent of another 2-hour course. As a result, about 3 weeks ago all the structures that I’d set up for doing GTD got totally overrun with "stuff". I’ve been going day-to-day with to-do lists and so forth, but I’m going to have to take some time over break and declare productivity bankruptcy, and start the whole GTD thing over again with a much, MUCH fatter "Someday/Maybe" file (which will consist of the stuff in my projects list that got crowded out by the constant grading/prepping cycle).
  • Yesterday I had another grading blitz and got lots done. But I still have four untended items for the geometry class to get done. When this will get done is anybody’s guess.
  • Mom and Dad are driving up today to stay until Saturday morning. They are bringing Doodlebug one of these, and I hope she likes it, because they seem pretty cool. On tap is a tour of the new house (almost finished!), dinner at our favorite Chinese place tonight, then probably hitting the Childrens’ Museum tomorrow and more sights in downtown. And since they’re staying at one of these, we’ve promised Doodlebug that swimming in the hotel pool is part of the deal.
  • I’m doing a workshop at the Indiana Council of Teachers of Mathematics meeting on Sunday in Indy on factoring, the division algorithm, and how they relate to cryptography. It’s nice because it’s virtually the same workshop that I gave to a similar group of high school teachers back in June. The sad thing is, with my GTD system fried, I actually had forgotten I was doing this until yesterday. Oops.

Comments Off on Fall Break overview

Filed under Crypto, Education, Engineering, Family, GTD, Higher ed, Life in academia, Math, Teaching