Keith Devlin: Fibonacci introduced modern arithmetic —then disappeared

More than a decade ago, Keith Devlin, a math expositor, set out to research the life and legacy of the medieval mathematician Leonardo of Pisa, popularly known as Fibonacci, whose book Liber abbaci has quite literally affected the lives of everyone alive today. Although he is most famous for the Fibonacci numbers—which, it so happens, he didn’t invent—Fibonacci’s greatest contribution was as an expositor of mathematical ideas at a level ordinary people could understand. In 1202, Liber abbaci—the “Book of Calculation”—introduced modern arithmetic to the Western world. Yet Fibonacci was long forgotten after his death. Finding Fibonacci is a compelling firsthand account of his ten-year quest to tell Fibonacci’s story. Devlin recently answered some questions about his new book for the PUP blog:

You’ve written 33 math books, including many for general readers. What is different about this one?

KD: This is my third book about the history of mathematics, which already makes it different from most of my books where the focus was on abstract concepts and ideas, not how they were discovered. What makes it truly unique is that it’s the first book I have written that I have been in! It is a first-person account, based on a diary I kept during a research project spread over a decade.

If you had to convey the book’s flavor in a few sentences, what would you say?

KD: Finding Fibonacci is a first-person account of a ten-year quest to uncover and tell the story of one of the most influential figures in human history. It started out as a diary, a simple record of events. It turned into a story when it became clear that it was far more than a record of dates, sources consulted, places visited, and facts checked. Like any good story, it has false starts and disappointments, tragedies and unexpected turns, more than a few hilarious episodes, and several lucky breaks. Along the way, I encountered some amazing individuals who, each for their own reasons, became fascinated by Fibonacci: a Yale professor who traced modern finance back to Fibonacci, an Italian historian who made the crucial archival discovery that brought together all the threads of Fibonacci’s astonishing story, an American math professor who fought against cancer to complete the world’s first (and only) modern language translation of Liber abbaci, and the widow who took over and brought his efforts to fruition after he lost that battle. And behind it all, the man who was the focus of my quest. Fibonacci played a major role in creating the modern commercial world. Yet he vanished from the pages of history for five hundred years, made “obsolete,” and in consequence all but forgotten forever, by a new technology.

What made you decide to write this book?

KD: There were really two key decisions that led to this book. One was deciding, back in the year 2000, to keep a diary of my experiences writing The Man of Numbers. My first history book was The Unfinished Game. For that, all I had to do was consult a number of reference works. It was not intended to be original research. Basic Books asked me to write a short, readable account of a single mathematical document that changed the course of human history, to form part of a series they were bringing out. I chose the letter Pierre De Fermat wrote to his colleague Blaise Pascal in 1654, which most experts agree established modern probability theory, in particular how it can be used to predict the future.

In The Man of Numbers, in contrast, I set out to tell a story that no one had told before; indeed, the consensus among the historians was that it could not be told—there simply was not enough information available. So writing that book would require engaging in a lot of original historical research. I had never done that. I would be stepping well outside my comfort zone. That was in part why I decided to keep a diary. The other reason for keeping a record was to ensure I had enough anecdotes to use when the time came to promote the book—assuming I was able to complete it, that is. (I had written enough popular mathematics books to appreciate the need for author promotional activities!)

The second decision, to turn my diary into a book (which only at the end found the title, Finding Fibonacci), came after The Man of Numbers was published in 2011. The ten-year process of researching and writing that book had turned out to be so rich, and so full of unexpected twists and turns, including several strokes of immense luck, that it was clear there was a good story to be told. What was not clear was whether I would be able to write such a book. All my other books are third-person accounts, where I am simply the messenger. In Finding Fibonacci, I would of necessity be a central character. Once again, I would be stepping outside my comfort zone. In particular, I would be laying out on the printed page, part of my inner self. It took five years and a lot of help from my agent Ted Weinstein and then my Princeton University Press editor Vickie Kearn to find the right voice and make it work.

Who do you expect will enjoy reading this book?

KD: I have a solid readership around the world. I am sure they will all read it. In particular, everyone who read The Man of Numbers will likely end up taking a look. Not least because, in addition to providing a window into the process of writing that earlier book, I also put in some details of that story that I did not fully appreciate until after the book had been published. But I hope, and in fact expect, that Finding Fibonacci will appeal to a whole new group of readers. Whereas the star of all my previous books was a discipline, mathematics, this is a book about people, for the most part people alive today. It’s a human story. It has a number of stars, all people, connected by having embarked on a quest to try to tell parts of the story of one of the most influential figures in human history: Leonardo of Pisa, popularly known as Fibonacci.

Now that the book is out, in one sentence if you can, how would you summarize writing it?

KD: Leaving my author’s comfort zone. Without a doubt. I’ve never been less certain how a book would be received.

DevlinKeith Devlin is a mathematician at Stanford University and cofounder and president of BrainQuake, an educational technology company that creates mathematics learning video games. His many books include The Unfinished Game: Pascal, Fermat, and the Seventeenth-Century Letter That Made the World Modern and The Man of Numbers: Fibonacci’s Arithmetic Revolution. He is the author of Finding Fibonacci: The Quest to Rediscover the Forgotten Mathematical Genius Who Changed the World.

Cipher challenge #2 from Joshua Holden: Subliminal channels

The Mathematics of Secrets by Joshua Holden takes readers on a tour of the mathematics behind cryptography. Most books about cryptography are organized historically, or around how codes and ciphers have been used in government and military intelligence or bank transactions. Holden instead focuses on how mathematical principles underpin the ways that different codes and ciphers operate. Discussing the majority of ancient and modern ciphers currently known, The Mathematics of Secrets sheds light on both code making and code breaking. Over the next few weeks, we’ll be running a series of cipher challenges from Joshua Holden. The first was on Merkle’s puzzles. Today’s focuses on subliminal channels:

As I explain in Section 1.6 of The Mathematics of Secrets, in 1929 Lester Hill invented the first general method for encrypting messages using a set of multiple equations in multiple unknowns.  A less general version, however, had already appeared in 1926, submitted by an 18-year-old to a cryptography column in a detective magazine.  This was Jack Levine, who would later become a prolific researcher in several areas of mathematics, including cryptography.

Levine’s system was billed as a way of encrypting two different messages at the same time.  Maybe one of them was the real message and the other was a dummy message–if the message was intercepted, the interceptor could be thrown off the scent by showing them the dummy message.  This sort of system is now known as a subliminal channel.

The system starts with numbering the letters of the alphabet in two different ways:

   a  b  c  d  e  f  g  h  i  j  k  l  m
  27 28 29 30 31 32 33 34 35 36 37 38 39
   1  2  3  4  5  6  7  8  9 10 11 12 13
  
   n  o  p  q  r  s  t  u  v  w  x  y  z
  40 41 42 43 44 45 46 47 48 49 50 51 52
  14 15 16 17 18 19 20 21 22 23 24 25 26

Suppose the first plaintext, or unencrypted message, is “tuesday” and the second plaintext is “tonight.”  We use the first set of numbers for the first plaintext:

   t  u  e  s  d  a  y
  46 47 31 45 30 27 51

and the second set for the second plaintext:

   t  o  n  i  g  h  t
  20 15 14  9  7  8 20

The encrypted message, or ciphertext, is made up of pairs of numbers.  The first number in each pair is half the sum of the two message numbers, and the second number is half the difference:

    t       u        e       s       d       a        y
   46      47       31      45      30      27       51
  
    t       o        n       i       g       h        t
   20      15       14       9       7       8       20
  
33,13    31,16  22½,8½   27,18 18½,11½  17½,9½  35½,15½

To decrypt the first message, just take the sum of the two numbers in the pair, and to decrypt the second message just take the difference.  This works because if P1 is the first plaintext number and P2 is the second, then the first ciphertext number is

and the second is

Then the plaintext can be recovered from the ciphertext using

and

This system is not as secure as Hill’s because it gives away too much information.  For starters, the existence and nature of the fractions is a clue to the encryption process.  (The editor of the cryptography column suggested doubling the numbers to avoid the fractions, but then the pattern of odd and even numbers would still give information away.)  Also, the first number in each pair is always between 14 and 39 and is always larger than the second number, which is always between ½ and 25 ½.  This suggests that subtraction might be relevant, and the fact that there are twice as many numbers as letters might make a codebreaker suspect the existence of a second message and a second process.  Hill’s system solves some of these issues, but the problem of information leakage continues to be relevant with modern-day ciphers.

With those hints in mind, can you break the cipher used in the following message?

11 3/5, 15 4/5   10 4/5,  9 2/5   17,     11        14 1/5, 16 3/5
 9 4/5,  7 2/5   12 3/5,  7 4/5    9 2/5, 12  1/5   13 1/5, 13 3/5
18,     11       12 2/5, 14 1/5    8 4/5, 10  2/5   12 1/5,  6 3/5
15 4/5, 12 2/5   13 3/5, 13 4/5   12,     16        11 2/5,  8 1/5
 9 1/5, 16 3/5   14,     17       16 3/5, 12  4/5    9 4/5, 14 2/5
12 1/5,  6 3/5   11 3/5, 15 4/5   10,     11        11 4/5,  6 2/5
10 2/5, 14 1/5   17 2/5, 12 1/5   14 3/5,  9  4/5

Once you have the two plaintexts, can you deduce the process used to encrypt them?

 

Answer to Cipher Challenge #1: Merkle’s Puzzles

The hole in the version of Merkle’s puzzles is that the shift we used for encrypting is vulnerable to a known-plaintext attack. That means that if Eve knows the ciphertext and part of the plaintext, she can get the rest of the plaintext. In Cipher Challenge #1, she knew that the word “ten” is part of the plaintext. So she shifts it until she finds a ciphertext that matches one of the puzzles:

ten
UFO
VGP

“Aha!” says Eve. “The first puzzle starts with VGP, so it must decrypt to ten!” Then she decrypts the rest of the puzzle:

VGPVY QUGXG PVYGP VAQPG UKZVG GPUGX GPVGG PBTPU XSNHT JZFEB
whqwz rvhyh qwzhq wbrqh vlawh hqvhy hqwhh qcuqv ytoiu kagfc
xirxa swizi rxair xcsri wmbxi irwiz irxii rdvrw zupjv lbhgd
yjsyb txjaj sybjs ydtsj xncyj jsxja jsyjj sewsx avqkw mcihe
                             ⋮
qbkqt lpbsb kqtbk qvlkb pfuqb bkpbs bkqbb kwokp snico euazw
rclru mqctc lrucl rwmlc qgvrc clqct clrcc lxplq tojdp fvbax
sdmsv nrdud msvdm sxnmd rhwsd dmrdu dmsdd myqmr upkeq gwcby
tentw oseve ntwen tyone sixte ensev entee nzrns vqlfr hxdcz

So the secret key is 2, 7, 21, 16.

The hole can be fixed by using a cipher that is less vulnerable to known-plaintext attacks. Sections 4.4 and 4.5 of The Mathematics of Secrets give examples of ciphers that would be more secure.