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.

CRT Capabilities and Limitations

Mathematical Foundations for Cryptography

Conoce a los instructores