I was traveling in Europe this week for business, London for three days and Paris for two. We actually had fantastic spring weather in London toward the end of the week. Absolutely fabulous! My wife's sister's family lives in Berkshire (expat Americans) and I got to see them Friday evening. We actually sat outside in the back yard and had nice BBQ.

In the course of flying over to Paris, I bought a book at Heathrow called In Code: A Mathematical Journey, by Sarah Flannery. Sarah was a teenage student in County Cork, Ireland, who's father is a math professor. She ended up doing some work on public key encryption schemes for a science faire she entered and won several large prizes world-wide. What is particularly interesting are some advances she made with respect to PK encryption using a matrix-based encryption scheme she later named the Cayley-Pursor algorithm. The CP algorithm is faster than RSA because its fundamental operations are based on multiplication, rather than exponentiation (RSA is notoriously slow, but regarded as being quite secure; an algorithm that would be just as secure but faster is highly interesting). The book recounts the story of her adventures with the media after she won several of these prizes. It also gives a nice introduction to number theory that is gentle enough for most anybody as she develops the project. While Sarah's algorithm was later found to have a couple of weaknesses that make it not as secure as RSA, it's all quite interesting.

Generally, Sarah seems like a very well-adjusted teenager (now in her 20s and at Cambridge) from a pretty well-adjusted Irish family. You'll find this book interesting if you like, math, encryption, or just good human interest stories about people and the world.

Anyway, the Lisp tie-in here (you know I had to get to that at some point), is that I was reading parts of this in the United Airlines lounge in Heathrow today (Saturday here in California, though it feels like Sunday to me this minute... ;-). In particular, there is a section on Fermat's Little Theorem. This theorem basically allows you to quickly test for whether a number is composite (is not prime) without having to try to factor it. Basically, you calculate 2^n-1 mod n. If that equals anything other than 1, you have a composite. If it equals 1, the number may still be a composite and you'll have to do more tests. Anyway, the book gave an example of testing whether the number 11111 is composite (it is: 41 * 271 = 11111). When you evaluate 2¹¹¹¹⁰ mod 11111, you get 10536 instead of one. So I just had to try this in Lisp. I fired up my laptop running CLISP and in the blink of an eye (this copied from SBCL):

* (mod (expt 2 11110) 11111)
10536

It's so nice to have a programming language that actually handles that without so much as a wimper.