Twenty Mathematicians, Two Hard Problems, One Week, IdeaLab2013 Friday, Aug 2 2013 

July has been an exciting and busy month for me. I taught number theory 3 hours a day, 5 days a week, for 3 weeks to (mostly) devoted and motivated high school students in the Summer@Brown program. In the middle, I moved to Massachusetts. Immediately after the Summer@Brown program ended, I was given the opportunity to return to ICERM to participate in an experimental program called an IdeaLab.

IdeaLab invited 20 early career mathematicians to come together for a week and to generate ideas on two very different problems: Tipping Points in Climate Systems and Efficient Fully Homomorphic Encryption. Although I plan on writing a bit more about each of these problems and the IdeaLab process in action (at least from my point of view), I should say something about what these are.

Models of Earth’s climate are used all the time, to give daily weather reports, to predict and warn about hurricanes, to attempt to understand the effects of anthropogenic sources of carbon on long-term climate. As we know from uncertainty about weather reports, these models aren’t perfect. In particular, they don’t currently predict sudden, abrupt changes called ‘Tippling points.’ But are tipping points possible? There have been warm periods following ice-ages in the past, so it seems that there might be tipping points that aren’t modelled in the system. Understanding these form the basis for the idea behind the Tipping Points in Climate Systems project. This project also forms another link in Mathematics of Planet Earth.

On the other hand, homomorphic encryption is a topic in modern cryptography. To encrypt a message is to make it hard or impossible for others to read it unless they have a ‘key.’ You might think that you wouldn’t want someone holding onto an encrypted data to be able to do anything with the data, and in most modern encryption algorithms this is the case. But what if we were able to give Google an encrypted dataset and ask them to perform a search on it? Is it possible to have a secure encryption that would allow Google to do some sort of search algorithm and give us the results, but without Google ever understanding the data itself? It may seem far-fetched, but this is exactly the idea behind the Efficient Fully Homomorphic Encryption group. Surprisingly enough, it is possible. But known methods are obnoxiously slow and infeasible. This is why the group was after ‘efficient’ encryption.

So 20 early career mathematicians from all sorts of areas of mathematics gathered to think about these two questions. For the rest of this post, I’d like to talk about the structure and my thoughts on the IdeaLab process. In later posts, I’ll talk about each of the two major topics and what sorts of ideas came out of the process.

(more…)

Chinese Remainder Theorem (SummerNT) Tuesday, Jul 9 2013 

This post picks up from the previous post on Summer@Brown number theory from 2013.

Now that we’d established ideas about solving the modular equation ax \equiv c \mod m, solving the linear diophantine equation ax + by = c, and about general modular arithmetic, we began to explore systems of modular equations. That is, we began to look at equations like

Suppose x satisfies the following three modular equations (rather, the following system of linear congruences):

x \equiv 1 \mod 5

x \equiv 2 \mod 7

x \equiv 3 \mod 9

Can we find out what x is? This is a clear parallel to solving systems of linear equations, as is usually done in algebra I or II in secondary school. A common way to solve systems of linear equations is to solve for a variable and substitute it into the next equation. We can do something similar here.

From the first equation, we know that x = 1 + 5a for some a. Substituting this into the second equation, we get that 1 + 5a \equiv 2 \mod 7, or that 5a \equiv 1 \mod 7. So a will be the modular inverse of 5 \mod 7. A quick calculation (or a slightly less quick Euclidean algorithm in the general case) shows that the inverse is 3. Multiplying both sides by 3 yields a \equiv 3 \mod 7, or rather that a = 3 + 7b for some b. Back substituting, we see that this means that x = 1+5a = 1+5(3+7b), or that x = 16 + 35b.

Now we repeat this work, using the third equation. 16 + 35b \equiv 3 \mod 9, so that 8b \equiv 5 \mod 9. Another quick calculation (or Euclidean algorithm) shows that this means b \equiv 4 \mod 9, or rather b = 4 + 9c for some c. Putting this back into x yields the final answer:

x = 16 + 35(4 + 9c) = 156 + 315c

x \equiv 156 \mod 315

And if you go back and check, you can see that this works. \diamondsuit

There is another, very slick, method as well. This was a clever solution mentioned in class. The idea is to construct a solution directly. The way we’re going to do this is to set up a sum, where each part only contributes to one of the three modular equations. In particular, note that if we take something like 7 \cdot 9 \cdot [7\cdot9]_5^{-1}, where this inverse means the modular inverse with respect to 5, then this vanishes mod 7 and mod 9, but gives 1 \mod 5. Similarly 2\cdot 5 \cdot 9 \cdot [5\cdot9]_7^{-1} vanishes mod 5 and mod 9 but leaves the right remainder mod 2, and 5 \cdot 7 \cdot [5\cdot 7]_9^{-1} vanishes mod 5 and mod 7, but leaves the right remainder mod 9.

Summing them together yields a solution (Do you see why?). The really nice thing about this algorithm to get the solution is that is parallelizes really well, meaning that you can give different computers separate problems, and then combine the things together to get the final answer. This is going to come up again later in this post.

These are two solutions that follow along the idea of the Chinese Remainder Theorem (CRT), which in general says that as long as the moduli are relative prime, then the system

a_1 x \equiv b_1 \mod m_1

a_2 x \equiv b_2 \mod m_2

\cdots

a_k x \equiv b_k \mod m_k

will always have a unique solution \mod m_1m_2 \ldots m_k. Note, this is two statements: there is a solution (statement 1), and the statement is unique up to modding by the product of this moduli (statement 2). Proof Sketch: Either of the two methods described above to solve that problem can lead to a proof here. But there is one big step that makes such a proof much easier. Once you’ve shown that the CRT is true for a system of two congruences (effectively meaning you can replace them by one congruence), this means that you can use induction. You can reduce the n+1st case to the nth case using your newfound knowledge of how to combine two equations into one. Then the inductive hypothesis carries out the proof.

Note also that it’s pretty easy to go backwards. If I know that x \equiv 12 \mod 30, then I know that x will also be the solution to the system

x \equiv 2 \mod 5

x \equiv 0 \mod 6

In fact, a higher view of the CRT reveals that the great strength is that considering a number mod a set of relatively prime moduli is the exact same (isomorphic to) considering a number mod the product of the moduli.

The remainder of this post will be about why the CRT is cool and useful.

Application 1: Multiplying Large Numbers

Firstly, the easier application. Suppose you have two really large integers a,b (by really large, I mean with tens or hundreds of digits at least – for concreteness, say they each have n digits). When a computer computes their product ab, it has to perform n^2 digit multiplications, which can be a whole lot if n is big. But a computer can calculate mods of numbers in something like \log n time, which is much much much faster. So one way to quickly compute the product of two really large numbers is to use the Chinese Remainder Theorem to represent each of a and b with a set of much smaller congruences. For example (though we’ll be using small numbers), say we want to multiply 12 by 21. We might represent 12 by 12 \equiv 2 \mod 5, 5 \mod 7, 1 \mod 11 and represent 21 by 21 \equiv 1 \mod 5, 0 \mod 7, 10 \mod 11. To find their product, calculate their product in each of the moduli: 2 \cdot 1 \equiv 2 \mod 5, 5 \cdot 0 \equiv 0 \mod 7, 1 \cdot 10 \equiv 10 \mod 11. We know we can get a solution  to the resulting system of congruences using the above algorithm, and the smallest positive solution will be the actual product.

This might not feel faster, but for much larger numbers, it really is. As an aside, here’s one way to make it play nice for parallel processing (which vastly makes things faster). After you’ve computed the congruences of 12 and 21 for the different moduli, send the numbers mod 5 to one computer, the numbers mod 7 to another, and the numbers mod 11 to a third (but also send each computer the list of moduli: 5,7,11). Each computer will calculate the product in their modulus and then use the Euclidean algorithm to calculate the inverse of the product of the other two moduli, and multiply these together.  Afterwards, the computers resend their data to a central computer, which just adds the result and takes it mod 5 \cdot 7 \cdot 11 (to get the smallest positive solution). Since mods are fast and all the multiplication is with smaller integers (no bigger than the largest mod, ever), it all goes faster. And since it’s parallelized, you’re replacing a hard task with a bunch of smaller easier tasks that can all be worked on at the same time. Very powerful stuff!

I have actually never seen someone give the optimal running time that would come from this sort of procedure, though I don’t know why. Perhaps I’ll look into that one day.

Application 2: Secret Sharing in Networks of People

This is really slick. Let’s lay out the situation: I have a secret. I want you, my students, to have access to the secret, but only if  at least six of you decide together that you want access. So I give each of you a message, consisting of a number and a modulus. Using the CRT, I can create a scheme where if any six of you decide you want to open the message, then you can pool your six bits together to get the message. Notice, I mean any six of you, instead of a designated set of six. Further, no five people can recover the message without a sixth in a reasonable amount of time. That’s pretty slick, right?

The basic idea is for me to encode my message as a number P (I use P to mean plain-text). Then I choose a set of moduli, one for each of you, but I choose them in such a way that the product of any 5 of them is smaller than P, but the product of any 6 of them is greater than P (what this means is that I choose a lot of primes or near-primes right around the same size, all right around the fifth root of P). To each of you, I give you the value of P \mod m_i and the modulus m_i, where m_i is your modulus. Since P is much bigger than m_i, it would take you a very long time to just happen across the correct multiple that reveals a message (if you ever managed). Now, once six of you get together and put your pieces together, the CRT guarantees a solution. Since the product of your six moduli will be larger than P, the smallest solution will be P. But if only five of you get together, since the product of your moduli is less than P, you don’t recover P. In this way, we have our secret sharing network.

To get an idea of the security of this protocol, you might imagine if I gave each of you moduli around the size of a quadrillion. Then missing any single person means there are hundreds of trillions of reasonable multiples of your partial plain-text to check before getting to the correct multiple.

A similar idea, but which doesn’t really use the CRT, is to consider the following problem: suppose two millionaires Alice and Bob (two people of cryptological fame) want to see which of them is richer, but without revealing how much wealth they actually have. This might sound impossible, but indeed it is not! There is a way for them to establish which one is richer but with neither knowing how much money the other has. Similar problems exist for larger parties (more than just 2 people), but none is more famous than the original: Yao’s Millionaire Problem.

Alright – I’ll see you all in class.