0:00

In this lesson, we're going to look at some of the useful things we can do with

Â the Chinese Remainder Theorem as well as

Â a few things that would be nice to do with it but that don't work out,

Â at least not very easily.

Â For simplicity, let's use 60 as our modulus and

Â partition that into CRT moduli of three, four, and five.

Â Next let's figure out the equation that will let us convert our CRT

Â residues back into a principal mod 60 residue.

Â You might want to pause the video here and figure this one out on your own.

Â Our equation turns out to be this linear combination of our residues.

Â Next, let's pick a couple of integers that we'll use in our examples,

Â say 23 and 46,

Â and find their CRT representations,

Â x is congruent to two, three,

Â three and y is congruent to one, two,

Â one in our three,

Â four, five CRT world.

Â For most of the rest of this lesson,

Â we'll indicate the modulus as just mod 60,

Â whether we are using a single modulus or our chosen CRT modulus.

Â This is actually pretty common practice when the specific moduli is clearly understood.

Â The first thing that might jump out at us is that even though 46 is larger than 23,

Â this isn't at all obvious from the CRT representations since

Â each of the moduli for 46 is less than those for 23.

Â The CRT is a poor representation if we need to determine the relative order of values.

Â Fortunately, we seldom need to do this since

Â the very concept of order is problematic in a modular world.

Â For instance, which is larger, 50 or 70?

Â Or plus three or minus three?

Â In an integer world,

Â the answer is obvious.

Â But in a mod 60 world,

Â every number is congruent to

Â an infinite number of other values both larger and smaller than it.

Â To further underscore this,

Â consider minus 20, 40, and 100.

Â These are all congruent to each other and therefore indistinguishable in a mod 60 world.

Â So none of them are larger or smaller than either of the others.

Â Two numbers that have particular significance in modular arithmetic are zero and one.

Â A little thought should convince you that regardless of the moduli,

Â zero is always represented as a CRT value consisting of all zero residues,

Â while one is represented by all one residues.

Â The representation of any other integer value depends on the choice of the moduli.

Â One thing that we do a lot is add and multiply numbers together in a module world.

Â So, can we do this in a CRT world and if so, how?

Â For instance, we want to add x and y to get z.

Â Let's look at how we determine each of the CRT residues

Â by focusing on just z3 for simplicity.

Â We know we can perform the reduction at any step we

Â want as long as we do it at the end as well.

Â This allows us to write the expression for z3 in terms of x3 and y3.

Â Since the best we can do is congruents,

Â we can find z3 by just adding x3 and y3.

Â Usually, of course, we'll reduce it by that residue's modulus.

Â So 23 plus 46,

Â which we can see a 69, which is congruent to 9,

Â which is a CRT value of 0,1,4,

Â adding the residues one-by-one yields the same result.

Â We can use our conversion formula to see the effect of

Â multiplying a CRT value by a normal integer.

Â The distributive property multiplication let's us see that we can just

Â multiply each residue by the integer and reduce by that modulus.

Â But what about when multiplying two CRT representative values?

Â The distributive property multiplication let's us see that we can just multiply

Â each residue by that integer and reduce by the modulus.

Â A simple example is multiplying 23, our value for x,

Â by two and seeing if we get 46,

Â our value for y.

Â But what about multiplying two CRT representative values together?

Â Here we can use our conversion equation to

Â good use by representing x and y using that equation.

Â We don't need to actually multiply these two equations out to determine what will happen.

Â The key is to note that the only terms that are not congruent to zero mod

Â three are 40x_sub_3 and 40y_sub_3.

Â So the product of these two terms is

Â the only one that will survive the reduction of z mod three.

Â Furthermore, since 40 is congruent to one mod three,

Â when we reduce the product mod three,

Â we will be left with x3 times y3.

Â The same pattern applies to all of the moduli.

Â Thus, we can multiply two CRT values by simply multiplying the respective moduli.

Â Direct multiplication of our x and y values yields

Â 1058 which reduces to 38 mod 60 which is 2,2,3.

Â Doing this using the CRT representations yields the same result.

Â What about multiplicative inverses?

Â Since we are looking for a CRT value that,

Â when multiplied by a given value,

Â must produce all one residues,

Â and since each multiplicative residue is obtained residue by residue,

Â it should be fairly obvious that to find the multiplicative inverse of a CRT value,

Â we only need to find the multiplicative inverses of

Â the individual residues with respect to their corresponding modulus.

Â Note that we still have the same issue that we always have.

Â A multiplicative inverse only exists if the number is relatively prime to the modulus.

Â In CRT, this requires that it be relatively prime to all of the individual moduli.

Â So let's find the multiplicative inverse of 23, our x value.

Â We can very easily find the inverses of each of the residues and then

Â use our conversion formula to find out that the result is 47.

Â Without the CRT, we would probably use

Â the extended Euclidean algorithm to find the inverse.

Â We can confirm that this is the inverse by multiplying out the CRT values,

Â which is very easy,

Â or we could deal with the integer values which is a bit more involved.

Â We spent quite a bit of time on exponentiation.

Â So how well does this translate into CRT values?

Â Like multiplication, if our exponent is an integer,

Â it becomes pretty obvious that we can just

Â exponentiate the respective moduli by that exponent.

Â This is based on how we multiply a CRT value by itself repeatedly.

Â For instance, taking the cube of 23,

Â we get a result of 2,3,2 which is congruent to 47.

Â But this is the multiplicative inverse of 23? Pure coincidence.

Â Doing the exponentiation directly,

Â we get the same result.

Â But what if the exponent is represented as a CRT value?

Â Here, we run into some problems.

Â One way to see how this comes about is to consider raising a simple integer,

Â say two, to a CRT represented value.

Â First off, our formula is intrinsically tied to

Â a mod 60 world but the exponent lives in a mod totient 60 world.

Â Modular reduction in another modulus does not work in general because this is

Â one of the instances in which the various members of a residue class are not equivalent.

Â For example, 20 and 80 are congruent mod 60,

Â but the totient of 60 is 16,

Â so 20 reduces to four while 80 reduces to zero.

Â Let's ignore this for a moment just so we can see this other issue I mentioned.

Â If we use our conversion formula,

Â we see this problem pretty quickly by noting that the addition

Â of exponents translates into multiplication of several factors.

Â Here we can't make any claims about the factors involving residues for the other moduli.

Â Hence, the moduli affect the results of the other moduli.

Â Thus, using CRT represent values as exponents is challenging.

Â There are techniques for doing this but they're

Â advanced topics beyond the scope of this course.

Â So for us, I'm calling this something we can't do using CRT.

Â If you're interested, you might look into what's known as the explicit CRT theorem.

Â Fortunately for me, practical applications of the Chinese Remainder Theorem,

Â such as RSA computations,

Â we can work in a mixture of CRT and non-CRT representations and

Â craft algorithms that yield significant speed up over pure non-CRT-based approaches.

Â