Prime numbers, beautiful and useful

Dear readers,

As my second interview had to be delayed due to the holidays, I am going to tell you instead about a topic that has always fascinated me by its simplicity, beauty and at the same time usefulness in real life. That topic is prime numbers. I will begin by describing some relevant theoretical results, then explain how they form the basis of modern online security, and then briefly discuss how quantum computers – if they ever come into existence – would force us to redesign a large number of our security systems.

First, let me remind you what prime numbers are. They are the numbers that are only divisible by 1 and themselves. Their sequence begins with 2, 3, 5, 7, 11, 13 and never ends, as the Ancient Greeks already knew. Indeed, if we supposed there were only finitely many of them, we could multiply them all and add 1 to get a result which would be larger than any of them, yet not divisible by any (because of the 1), leading to a contradiction. This proof technique is called reductio ad absurdum. In fact, the great Dirichlet showed that there are infinitely many primes in any arithmetic progression (a sequence you start with a number, called the first term, and keep adding another number, called the difference – for example, if the first term is 2 and the difference 3, you get 2, 5, 8, 11, etc), as long as the first term and the difference are integer and have no common factors. In 2004, Ben Green and Terry Tao showed that there are in fact arbitrarily long sequences of consecutive primes in arithmetic progression (a different and somewhat more surprising result because of the requirement that the primes be consecutive).

So what makes the primes important? They are the building blocks from which all integers are made. As you may remember from grade school, every integer can be factored into primes – and not only that, but this factoring is unique except for the order. The second property is not always true in other number systems. And now we get to the crux of the modern cryptographic protocols. While checking that a given number is prime is easy (fast on a modern computer), and multiplying numbers is easy as well, factoring an integer that is composed of as few as two primes can be hard (even with a supercomputer).

How can we check that a number is prime? There are some properties that a prime number satisfies, and few composite numbers satisfy them. One such property comes from Fermat’s little theorem, not to be confused with Fermat’s (in)famous last theorem, which states that if p is prime then ap-1-1 is divisible by p for any a between 1 and p-1. On the other hand, it turns out that if p is not prime, then fewer than half of all the possible bases a between 1 and p-1 still satisfy this property (such numbers p are called pseudoprimes to the base a), unless you happen to be very unlucky. So, by performing a number of tests with random bases one can determine with a great degree of confidence whether a given number p is prime. This approach is an example of a probabilistic algorithm, one which gives the right result with high probability if repeated many times. Interestingly, the first fast deterministic (not chance-based) algorithm for testing primality was found only in 2002, by two undergraduate students at the Indian Institute of Technology Kanpur, Neeraj Kayal and Nitin Saxena, and their advisor, Manindra Agrawal.

If you’ve watched a security certificate being generated on your computer (which generally takes a few seconds, depending on the certificate’s “grade”), here is exactly what happens – it produces two large numbers, checks that they are both prime (there are enough prime numbers to go around – if you want a 128-bit number you need to check about 100 candidates on average, by the prime number theorem) and multiplies them together. This gives you your “public key”, which you can share freely with the world. It allows other people to send you messages by encrypting them with your public key; however, since getting the original two prime numbers from your public key is hard (only your computer knows them because it generated them in the first place), you are the only one who can actually decrypt them!

This, in a nutshell, is the RSA system, named for MIT researchers Rivest, Shamir and Adleman. They are given the credit for publishing it first, but it had already been known to Clifford Cocks who, however, could not publish it because he worked for the British intelligence. Public-key cryptography was a revolutionary advance in technology – now you no longer need to worry about your encrypted messages being intercepted, because decrypting them is all but impossible – but it relies on the fact that factoring large numbers is hard. We believe that this is true with ordinary computers, though we cannot prove it for sure. This is where yet another surprise came in 1994: Shor’s quantum factoring algorithm!

Without going into details about quantum computers, let me just say that they are a very special mode of computation which relies on the quantum states of particles. While a regular bit has only two states, 0 and 1, a quantum bit (qubit for short) can exist in a superposition of these states (for an idea of what superposition is, think about two different sound frequencies you can hear at once), and only when it’s measured does it collapse to a well-defined state (the so-called collapse of the wave function). Now, it turns out that some things that are difficult to do on a regular computer are easier on a quantum one. And factoring large numbers just happens to be one of those things, as shown by Peter Shor in 1994. It is another probabilistic algorithm, and only requires a quantum computer large enough to write down the integer to be factored twice. For instance, for numbers of the size we discussed, this is 500 qubits.

Where does this leave us and our security systems? Well, on the one hand, quantum computers are still in their infancy as far as the technology goes (this is one field where theory has far outpaced practice), and the largest one in existence today cannot factor numbers greater than 100. On the other hand it may well happen that the technology will one day evolve to being able to build large quantum computers, so that all our security systems will be easily broken. If that happens, it may be necessary to also use quantum computers for building new security systems. Meanwhile, there are alternative systems being developed such as elliptic curve cryptography (the same elliptic curves used by Wiles to prove Fermat’s last theorem, which are plane curves defined by the equation y2 = x3 + ax + b). Perhaps not surprisingly, they also rely on prime numbers – but in a rather different way. Namely, they are based on counting the remainders that points on the elliptic curve can have when they are divided by a prime number.

Godfrey Harold Hardy, author of the famous and delightful book “A mathematician’s apology”, spent most of his life working on prime numbers (including the notorious and still unresolved Riemann hypothesis), prided himself on the lack of practical applications of his work. He notably said, I have never done anything ‘useful’. No discovery of mine has made, or is likely to make, directly or indirectly, for good or ill, the least difference to the amenity of the world”. Ironically, some of his work on prime numbers has turned out to be quite useful, and in my opinion, it is a credit to mathematicians, both pure and applied, that such a beautiful topic has also found such important applications in our everyday life.

Is a Museum of Mathematics necessary?

Dear readers,

Today, 12/12/12, is an important date for mathematics in the USA. Not just because it is a date which has three identical components (something that we won’t see again for another 88-odd years), and not even because it’s one of the 12 dates every year that are abbreviated the same way in the USA and the rest of the world (where, as you likely know, they are written with the days before the month). It is also significant because it marks the opening ceremony of the Museum of Mathematics in New York City.

If you read the New York Times, you may recognize the title of this post as a play on an article that appeared there this past summer, entitled Is Algebra Necessary? This misguided and naïve article was among the motivating factors for this blog, as it made me realize how undervalued and misunderstood mathematics education is even among the educated. Several good rebuttals to this article failed to get a larger conversation started, and it is this larger conversation that I want to contribute to with this blog.

Mathematics education is a topic I plan to address from many different angles next year, but for today, I will simply discuss whether a Museum of Mathematics is a step in the right direction. Glen Whitney, the museum’s director, told the New York Times that its mission is to shape cultural attitudes and dispel the bad rap that most people give math – which happens to be one of my blog’s objectives as well, so I could not agree more with his motivation. The big question is whether a museum can achieve this goal.

My main concern is that an appreciation for mathematics is unlikely to come from visiting exhibits in a museum – rather, I believe it can only appear from positive exposure to mathematics in everyday life. If a child dislikes the subject in school, they may expect going to a math museum to be boring. Just as with art, music or a language, a taste for mathematics is an acquired one. It usually requires a certain level of maturity and discipline, which children are unlikely to acquire without outside encouragement.

For this reason, parental influence, as well as that of peers, is critical. An environment that views math in a positive light will have its effect with or without the museum, while a hostile environment may not prepare a child for being receptive towards the museum’s exhibits. Without innovative changes in the mathematics curriculum, a more favorable attitude towards the subject, and a deeper understanding of the role of mathematics in our culture, the impact of the Museum of Mathematics may remain limited.

Despite my skepticism I remain open-minded. On my upcoming trip to New York City I will make sure to stop by the museum and see how deeply its exhibits engage me. I will report on my experience in an upcoming blog post, so stay tuned. Perhaps abstract concepts really can be made fascinating – and concrete – in a museum setting. I am just not sure that the museum can make enough of a difference.

There is, however, at least one thing that I’m pretty sure about. Dr. Whitney spent a decade working at an investment firm, and, in his own words, decided to engage in an activity with “more direct socially redeeming value”. While the social impact of his current undertaking may be limited, it will at least be significantly more positive than that of his previous job. And that, in itself, is definitely a good thing!

Mathematicians say the darndest things!

Dear readers,

If you have mathematically inclined friends or are mathematically inclined yourself, you may know that mathematicians tend to use a very specialized language when discussing their work. This is not a matter of trying to make the subject of discussion appear inaccessible to outsiders (though sometimes there is an element of that). Instead, it’s a communication necessity: everyday language is even more inadequate for discussing mathematics than it is for discussing topics such as music, philosophy or law.

But the terms used in mathematics are rarely invented from scratch; a great number of them are in fact taken from everyday language, but given different meanings. This is why you might hear words like filter (in lattice theory), flag (in linear algebra), ring (in abstract algebra), saddle (in calculus and analysis), sheaf (in topology), soul (in geometry), at a mathematics lecture. Their meanings, though usually inspired by natural language, frequently drift to the point of becoming unrecognizable.

Fortunately, this exchange between mathematics and natural language is a two-way street, and today I’m going to discuss some of the words that mathematicians often use in day-to-day conversations that are derived from mathematical terms. Using them might make you sound strange, but it might also help you express things concisely. I present to you the top 5 words I’ve heard used in conversations between mathematicians (and have been guilty of using myself in conversations with non-mathematicians on occasion). Whether you decide to adopt them or not, you’ll find it illuminating to know their meanings.

Mathematical meaning: as the independent variable becomes arbitrarily large.
Colloquial meaning: in the long run; looking at the big picture.
Example 1: Since he’s not staying in academia, having his name on papers is asymptotically irrelevant.
Example 2: They do have a significant age difference, but asymptotically it won’t matter all that much.

Mathematical meaning: an easily derived logical consequence of a proven result or theorem.
Colloquial meaning: something that follows automatically; something you get for free.
Example 1: If she gets invited to this wedding, her significant other’s presence will be a corollary.
Example 2: I just bought myself a new bicycle, and this water bottle came as a corollary.

Inflection point
Mathematical meaning: the point on a curve at which the second derivative changes sign.
Colloquial meaning: a situation where each new unit of effort affects the result less than the one before.
Example 1: I could have stayed up all night to finish it, but I don’t like to work past my inflection point.
Example 2: We’ve been working for ten hours and the inflection point is getting close; let’s call it a day.

Mathematical meaning: the remainder of the division of a given quantity by another (fixed) quantity.
Colloquial meaning: minor details that must be dealt with as a condition for getting a desired outcome.
Example 1: I will definitely join you at the basketball game tonight modulo finishing this assignment.
Example 2: I got the job modulo the background check and some annoying paperwork.

Mathematical meaning: perpendicular; in probability theory, uncorrelated (refers to random variables).
Colloquial meaning: unrelated; independent.
Example 1: Your observation is very interesting, but it’s orthogonal to the question we are discussing.
Example 2: How important a task is is often orthogonal to how urgent it appears to be.

Are there any other mathematical terms you like to use in everyday life? Share them in the comments!