The Chinese Remainder Theorem With Limits

Sun Tzu is famous for the discovery of the Chinese Remainder Theorem (CRT) in China in the third century, way before it was known in the west. His original example was:

How many soldiers are there in Han Xing’s army? — If you let them parade in rows of 3 soldiers, two soldiers will be left. If you let them parade in rows of 5, 3 will be left, and in rows of 7, 2 will be left.

For those of us who have a european-centric view of mathematics this should come as a warning. No one has a monopoly on ideas. No one. Since modern crypto-systems are based on number theory, our lack of a monopoly in this area raises a real security issue. If those who do identity theft were able to obtain the right number theory secrets, for example, we would have a potential disaster—I will discuss this another time.

Today I want to talk about two results related to the CRT. One is an old—well not old as in third century old—result due to Don Coppersmith, and the other is an observation about CRT with restrictions. The latter is really a way of raising the problem of integer factoring again. Are you surprised?

The CRT is one of my favorite theorems, but also one of my least favorite theorems. I have used the CRT theorem so many times that once Avi Wigderson said, “it’s the only theorem you know.” Avi says he never said this, but I recall him saying it. I could be wrong, but I kind of like the statement—so I will stick to my memory.

The CRT is one of my least favorite theorems, Avi’s comment notwithstanding, since it makes the task of understanding computation modulo composites hard. One of the open problems of complexity theory is what is the power of computing with gates modulo a composite? The CRT shows that the structure of , for example, is a direct product , but that is not very helpful. For example, suppose we need to understand the structure of the solution set to equations like

where are boolean and is a polynomial. The CRT does not seem to help here. The problem is this: the direct product of two boolean vectors need not be boolean. For instance, a vector can be boolean modulo and boolean modulo , but not boolean modulo .

I recently posted on a paper that will appear at FOCS on a related problem.

Solving an Equation Modulo

There is a wonderful theorem, due to Coppersmith, that should be in all our tool boxes.

Theorem: Let be a natural number and a monic polynomial of degree . Set for some . Then, there is an algorithm to find all satisfying

The running time is polynomial in .

The power of Coppersmith’s theorem is that can be composite. If has known factorization, then there are better methods for solving equations modulo —using CRT. See Dan Boneh’s survey on this theorem and related results.

CRT with Limits

Suppose that is a list of pairwise relatively prime natural numbers. Define to be equal to

The famous CRT theorem shows that for any there is a unique so that and for all indices ,

In the original problem, of Sun Tzu, , which are clearly relatively prime.

We are interested in allowing the constraints on modulo to be more flexible. Rather than a single value , we will allow to have any value in some set. Let be a list of sets so that each is contained in . We plan to replace (1) with the following,

Note, the classic CRT is just the case where each set is a singleton set. This generalization is uninteresting without some additional restriction. Note that the existence easily follows in this case because we can select some for each and there will be an satisfying (2).

The additional constraint that we will add, first, is the constraint on the size of . A natural constraint is force to be in where . The obvious algorithm for this problem would be: select and then find the unique ; then, check whether or not . If it is then stop; otherwise, try another selection.

The difficulty with this simple algorithm is that there could be an exponential number of choices, and so the algorithm could take too long. We will show how to do better, provided two things are true: (i) the value of is not too small compared with , and (ii) the inequality is replaced by a “softer” constraint. I will explain this shortly.

Define to be the set of so that

and for each index ,

Note, may or may not be empty: it depends on the sets and the limits in size on . Also we will often drop the and just write when there can be no confusion. Let be the maximum of the ‘s.

Theorem: Let and be as above, and let and . Then, there is an algorithm that runs in time . The algorithm operates as follows:

1. If is nonempty, then the algorithm returns an element of this set;
2. If is empty, then the algorithm returns “none”.

Note, the algorithm essentially finds an in the given range that satisfies a series of constraints modulo each relatively prime number. The complication in the statement of the theorem is that the inequalities on the solutions are not sharp. It is like a “no-man’s land”. If there is a solution in the range, the algorithm finds it; if there is no solution even near the range, the algorithm says none. For solutions in between the algorithm is allowed to fail.

Constructive CRT

The algorithm is based on the constructive version of the CRT. Consider a system of equations,

where . For each there is a so that . This follows since each is relatively prime to . Define,

The claim is that is a non-negative solution to all the equations (3). This follows since is equal to

which is congruent to modulo : the first sum’s terms are all modulo

Note, need not be less than , but for some ,

is in . The question that we need to understand is: when is this in the range ? The key is the following simple lemma: ( denotes the fractional part of )

Lemma: There is a solution to the equations (3) in the range if and only if

Proof: First, assume that (3) has a solution in the given range. Then, we must show that (4) is true. Clearly, for some non-negative , . This follows by the CRT uniqueness and that . Then, it follows that

The sum is clearly equal to where and is a natural number. I claim that . If this is true (4) will clearly follow, since is just the fractional part of the sum. We know that

Thus, if , then the last inequality would be false; and if , then the first would be false. Hence, the claim follows.

Second, assume that (4) is true. Then, we must show that (3) has a solution in the given range. We know that

which implies that where again is value of the sum. Further as before and is a natural number. But, clearly by the assumption. I now claim that

is a solution to all the congruences and that satisfies the required inequalities. The first is easy, so let’s turn to the inequalities. Again is equal to

But, this is just by definition. Thus, , and we are done.

The Algorithm

We can now explain the algorithm. The basic idea is to use a BDD type approach and encode the problem of finding into a finite state automaton. The input is in the form

where each is at most bits. The automaton reads each input and does two things. First, it checks that is in the current set . Second, it will compute the fractional part of

The first is easy and only uses order states. The second requires the automaton to compute the sum of rational numbers. This cannot be done exactly, but can be done to some fixed precision. At the end the machine accepts if and only if the first part is correct and also if the fractional part is less than .

The details will be worked out in a detailed note that I will post shortly. However, I hope you see the basic idea that is being done. Also it should be clear now why the “soft” inequality is needed. The sum could be very close to the value of and this could cause an error. So to avoid this we need a gap.

Open Problems

Can we improve the CRT with limits? Even as stated does it have some interesting applications? Note, one easy extension that might be interesting. We can add another type of constraint on . Let correspond to

Then, we can also add the constraint that for any boolean function that can be computed by a finite state automaton in polynomial number of states. Thus, we could check that there are an even number of ‘s in each , or that no .