0:00

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.

Â