In this lesson on the Chinese remainder theorem,

we'll explore the restrictions that exist on the choice of moduli available to us.

We'll also learn how to convert from a CRT representation to the integer or

more precisely the class representative that it corresponds to.

That will prepare us for the next lesson where we will examine some,

though certainly not all, of the things that CRT is well suited for and

also some of the things that it isn't.

Again, certainly not all.

In the prior lesson we didn't place any restrictions on the choice of our moduli

and so you might have found yourself wondering if, given arbitrary choices for

the CRT moduli, whether all CRT residues are actually possible.

Certainly, there is nothing that prevents us from writing down

any CRT residue we want.

But it is only useful if it corresponds to some subset of the integers.

So let's consider what would happen if we chose as our moduli 6 and 9.

This would seem to indicate that we can represent up to 54 different integers.

Or 54 equivalence classes.

But are we guaranteed none of these classes are empty?

That each class actually contains integers.

We have this guarantee provided but knowing one of the residues

places no restrictions on what any of the others can be.

Now might be a good time to pause the video and see if you can decide whether we

can uniquely represent the integers 0 through 53 as CRT residues

using 6 and 9 as our moduli and if not, why not?

And also how many non empty CRT equivalence classes are there?

So let's say that we choose x such that x mod 6 is 0.

This means that we know that the number is divisible by 6 which means that it is

also divisible by three.

But any number that is divisible by three can only have a mod 9 residue of 0,

3, or 6.

None of the others are possible.

So, for example, the equivalence class corresponding to the CRT encoding

0,1 is empty because it is not possible for an integer

to have a mod 6 residue of 0 and also a mod 9 residue of 1.

The residues of an integer using two different moduli are independent

only if the two moduli are relatively prime, that they share no common factors.

Thus the set of moduli that we use in any CRT representation must be pairwise

co-prime, meaning that none of them share a common factor with any of the others.

Going back to our choice of 6 and 9, these share a common factor of 3.

We can keep the 3 in one of the moduli, but

we must divide it completely out of all of the others.

The only way to do this gives us 2 and 9, since the only other choices would be

6 and 1 or 1 and 18, both of which are just normal modular worlds.

Although, that does show that a normal modular world is a CRT world,

just one that is pretty boring as it only has one meaningful modulus.

Thus we see that we actually only have 18 encodings.

Next let's set about calculating a CRT residues class representative, or

more informally, converting a sequence of CRT residues to the corresponding integer.

So we have an unknown value of x and known values of R1 and

R2 as well as known values of M1 and M2 that are co-prime.

Since we are in a mod in world, the best we can do is recover one of the values

in the same congruence class as the actual value of x.

Naturally, we'll opt for the class representative.

The overall modulus is, therefore, the produce of M1 and M2.

So how can we find x?

We'll start off by setting up a linear equation in which each individual

residue is multiplied by some coefficient And the products are then summed together.

This results in an equation in which each term contains the information about

exactly one of the residues, and

therefore each term corresponds to exactly one of our CRT moduli.

Since we are looking for

the least residue, we need to reduce the sum by our overall modulus in.

In general we have k moduli and hence one term for each corresponding residue.

The overall modulus is the product of the k individual moduli.

Now our task is to find suitable coefficients.

The key in this quest is to make sure that our equation

reduces to the proper residues for each modulus.

After all, any integer that reduces to this sequence of residues is,

by definition, in that CRT residue's equivalence class, and

since we have reduced this integer by the overall modulus we know that it is

the least residue, or class representative, of that equivalence class.

We can guarantee this outcome,

as long as each of the coefficients satisfy two constraints.

First, each term that does not contain the residue for

a given modulus must vanish when reduced by that modulus.

This requires that each coefficient be congruent to zero for

every modulus Except the one corresponding to the residue it contains.

Second, the term that does contain the residue for

a given modulus is must reduce suggest that residue when reduced by that modulus.

This requires that each coefficient be congruent to 1 for

the modulus corresponding to the residue it contains.

So let's set about making this happen.

We know that any term that is a multiple of a modulus

is concurrent to 0 when reduced by that modulus.

Now consider that N, our overall modulus, is the product of all of the moduli.

Hence, if we divide N by a given modulus,

what we have is a value that is the product of all the other moduli.

And therefore is congruent to 0 when reduced by

any of the other moduli except the one we divided by.

We can satisfy our first requirement by exploiting this fact.

Multiplying each terminar linear equation by the appropriate factor therefore

guarantees that when we reduce the equation by the various moduli

that each CRT moduli is a function of exactly one term and

that it is the term that contains the correct residue.

But since it may not be the correct value, we still have another factor,

A prime, that we need to determine for each coefficient.

So the final value of Ai is the product of A prime and

our ratio of the overall modulus to that term's CRT modulus.

Even without knowing what A prime is, we know that Ai is congruent to 0 for

all of the moduli other than Mi.

But we have no basis for believing that Ai is congruent to 1 when

we reduced mod Mi but that's a pretty easy error to fix.

To satisfy the second requirement,

we exploit the fact that the product of any integer and

its modular inverse is congruent to one when reduced by that modulus.

But this requires that the modular inverse actually exist which, in turn,

requires that our integer be relatively prime to Mi.

However, we have that covered,

since our integer is the overall modulus divided by the current CRT modulus.

Since each CRT modulus is relatively prime to all of the other CRT moduli,

it is also relatively prime to the product of all of them.

In fact, this is why the moduli must be pairwise co-prime.

If they aren't, we then have some coefficients that won't exist.

Our final expression for our coefficients is simply the product of the overall

modulus divided by that term's CRT modulus.

Then multiplied by the multiplicative inverse of that ratio in that

term's CRT modulus' world.

We can then reduce this by the overall modulus, though this isn't essential,

since we will do this again after evaluating the entire

linear equation for x.

We already know that Ai is congruent to 0 for all of the other moduli, but

you should now be confident that it also congruent to 1 for that term's moduli.

We can now summarize the central relations associated with

the Chinese Remainder Theorem quite succinctly.

Going forward, our modulus is the product of k relatively primed CRT moduli and

our C representation of x is a sequence of residues, one for each CRT modulus.

To go from the CRT residues back to x, or at least its class representative, we

evaluate a linear equation, and reduce it mod N, in which each of the coefficients

in our linear equation is found according to the process we just developed.

Let's apply what we've learned, and found the class representative for

the CRT value (2, 7, 19) in a (mod (4, 9, 25)) world.

First, we need to find the overall modulus

which we just multiply the three moduli and we get 900.

Next we need to find each coefficient.

For the modulus of 4, we divide 900 by 4 to get 225.

Next we find the mod for inverse of 225,

which turns out to be 1, since 221 itself is congruent to 1 in a mod 4 world.

Next we get our final coefficient for the first CRT modulus by multiplying 225 and

one to get 225.

And reduce it mod 900 which leaves us with 225.

Finding the coefficient for the modulus of 9 is very similar and

I recommend that you pause here and see what you get before continuing.

The second coefficient associated with the modulus of 9 is 100.

While the final coefficient corresponding to the modulus 25 is 576.

That gives us our final general equation for a mod 4925 world and

when we evaluate it for our particular residues, 2, 7 and 19, we get 394.

A quick check confirms that 394 does indeed belong in the 2,

7, 9 residue class.

I recommend that you play around with CRT transforms a bit before going on to

the next lesson, in which we explore some of the things that we can and

can't do with the Chinese remainder theorem.

Moduli Restrictions, CRT-to-Integer Conversions

Mathematical Foundations for Cryptography

与讲师见面