Welcome to the module on the Chinese Remainder Theorem. The Chinese Remainder Theorem or CRT dates back to the third century AD when it was discovered by the Chinese mathematician, Sunzi Suanjing. It has applications in many fields, but of course, we're going to focus our foray on the world of cryptography. In this module, over the next few lessons, we'll see that the CRT is yet one more way of representing integers, how we use the CRT to represent integers, and that the CRT lets us examine some very useful aspects of those integers. Naturally, we'll also learn how to convert a CRT-represented integer back into our everyday representation. We'll also examine some of the things we can do with CRT-represented integers, as well as some of the things that we can't. So without further delay, let's get started. We have several ways of representing numbers, integers in particular, and most of them provide specific insight into the structure of the number, often while hiding other aspects. There's no perfect representation. Consider briefly what the prime factorization tells us by looking at a couple of values. We can easily determine if X is divisible by Y, and if it is, what the prime factorization of the quotient is. The answer in this case, of course, is no. What about determining the greatest common divisor of X and Y? This is literally child's play using this representation. Many other questions can be answered just as easily. But what about such seemingly simple questions like whether X is greater than Y, or what the sum of two numbers is? By having different ways to represent integers, each with its strengths and weaknesses, we build up a toolkit of mathematical tools that allow us to use the right tool for the right job. After all, if the only tool we have is a hammer, then every problem looks suspiciously like a nail. We can do better. But choosing the right tool requires we understand both the strengths and weaknesses of each tool at our disposal. Let's ease our exploration of the Chinese Remainder Theorem by playing a simple game. I'm thinking of a number which means an integer that is at least zero, a number that is less than 900. I inform you that if I divide this number by 25, the remainder is 19. Similarly, the number reduced modulo nine is seven, and in a mod four world, the number is congruent to two. What number am I thinking of? You might want to pause the video at this point and see if you can figure it out. Let's look at what the first piece of information tells us. In a mod 25 world, only one number in 25 is congruent to 19. This means that of the 900 possible values under consideration, I've just eliminated 96% of them, and we only have 36 potential candidates left. Similarly, knowing that the remainder mod nine is seven eliminates eight ninths of those 36, leaving us with only four possibilities. Finally, knowing the residue mod four will leave us with just one possible value, but which one? Let's set that very important question aside until after we learn how to represent an integer using CRT. Let's look at the set of integers that we can represent with the three moduli from our game, namely, 4, 9 and 25. Let's first pick a number at random, say, 739 and find the residues for each of these moduli. Listing them as a sequence ordered from smallest modulus to largest, we get 3, 1 and 14. This is known as the modulo 4, 9, 25 CRT residue for the integer 739. Can we represent any integer using these moduli? Yes, because we can certainly reduce any integer by each of the moduli. But is there a unique mapping between any integer and its CRT representation? No, and for the same reason that we can't represent every integer uniquely in a modulo world. There are a finite number of residues in that world. Thus, all integers will fall into one of a set of equivalence classes in which the member of the set are indistinguishable from each other. So how many equivalence classes are there in our modulo 4, 9, 25 CRT world? Counting the number of different representations is simple. The first residue can take on four different values, the second one nine, and the third 25. Thus, we have 4 times 9 times 25 or 900, the product of the moduli, different CRT encodings using this modulo set. Just as we normally do with modular arithmetic, we will use the least residue system, meaning that we will choose the smallest nonnegative integer in each equivalence class as that class's representative. So when we convert from CRT back to an integer, what we will be finding is that CRT residues class representative, which will be a nonnegative integer strictly less than the product of the moduli. The CRT also exposes some of the finer details of the structure of the integer. In a normal mod-N world, if a integer is congruent to zero mod N, then we know that all of the integers in that equivalence class are evenly divisible by N. In CRT, we have multiple moduli, and if any of them are zero, we know that the integer is evenly divisible by that modulus. So we can easily see numbers that are evenly divisible by multiple moduli, not just the overall. This is as good a place as any to bring this introductory lesson on the Chinese Remainder Theorem to a close. So let's take a quick glance at what we've learned so far and what we still have to look forward to. We've seen that CRT is really nothing more than a slightly different way of representing integers within a mod N world, where the modulus is the product of a set of smaller moduli, and in which we represent the integer as a sequence of residues, one for each modulus. In doing so, we get a finer look into the structure of the integer. In particular, we can immediately identify those integers in the larger mod N world that are divisible by one or more of the smaller moduli. In the remainder of this module, we'll explore some of the restrictions we have to abide by when choosing our moduli and how to convert a CRT-represented integer into its class representative. Once we have that, we'll take a brief look at some of the things we can do with CRT and how CRT can make many of them easier. But we'll also take a look at some of the things that CRT is not well suited for.
