Coppersmith’s theorem and adding size constraints to the Chinese Remainder Theorem

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 ${\mathbb{Z}_{6}}$, for example, is a direct product ${\mathbb{Z}_{6} = \mathbb{Z}_{2} \times \mathbb{Z}_{3}}$, but that is not very helpful. For example, suppose we need to understand the structure of the solution set to equations like

$\displaystyle f(x_{1}, \dots, x_{n}) \equiv 0 \bmod 6$

where ${x_{1},\dots,x_{n}}$ are boolean and ${f}$ 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 ${2}$ and boolean modulo ${3}$, but not boolean modulo ${6}$.

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

Solving an Equation Modulo ${N}$

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

Theorem: Let ${N}$ be a natural number and ${f \in \mathbb{Z}[x]}$ a monic polynomial of degree ${d}$. Set ${X = N^{\frac{1}{d}-\epsilon}}$ for some ${\epsilon \ge 0}$. Then, there is an algorithm to find all ${0 satisfying

$\displaystyle f(x) \equiv 0 \bmod N.$

The running time is polynomial in ${\min(\log N, 1/\epsilon)}$.

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

CRT with Limits

Suppose that ${Q=(q_{1},\dots,q_{m})}$ is a list of pairwise relatively prime natural numbers. Define ${\Pi(Q)}$ to be equal to

$\displaystyle \prod_{i=1}^{m} q_{i}.$

The famous CRT theorem shows that for any ${A=(a_{1},\dots,a_{m})}$ there is a unique ${X}$ so that ${0 \le X < \Pi(Q)}$ and for all indices ${i}$,

$\displaystyle X \equiv a_{i} \bmod q_{i}. \ \ \ \ \ (1)$

In the original problem, of Sun Tzu, ${q_{1}=3, q_{2}=5, q_{3}=7}$, which are clearly relatively prime.

We are interested in allowing the constraints on ${X}$ modulo ${q_{i}}$ to be more flexible. Rather than a single value ${a_{i}}$, we will allow ${X}$ to have any value in some set. Let ${S=(S_{1},\dots,S_{m})}$ be a list of sets so that each ${S_{i}}$ is contained in ${\{0,1,\dots,q_{i}-1\}}$. We plan to replace (1) with the following,

$\displaystyle X \bmod q_{i} \in S_{i}. \ \ \ \ \ (2)$

Note, the classic CRT is just the case where each set ${S_{i}}$ 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 ${a_{i} \in S_{i}}$ for each ${i}$ and there will be an ${X}$ satisfying (2).

The additional constraint that we will add, first, is the constraint on the size of ${X}$. A natural constraint is force ${X}$ to be in ${[0,L]}$ where ${L < \Pi(Q)}$. The obvious algorithm for this problem would be: select ${a_{1} \in S_{1}, \dots, a_{m} \in S_{m}}$ and then find the unique ${X}$; then, check whether or not ${X. 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 ${L}$ is not too small compared with ${\Pi(Q)}$, and (ii) the inequality ${X is replaced by a “softer” constraint. I will explain this shortly.

Define ${\Gamma(Q,S,a,b)}$ to be the set of ${X}$ so that

$\displaystyle a \cdot \Pi(Q) \le X \le b \cdot \Pi(Q)$

and for each index ${i}$,

$\displaystyle X \bmod q_{i} \in S_{i}.$

Note, ${\Gamma(Q,S,a,b)}$ may or may not be empty: it depends on the sets and the limits in size on ${X}$. Also we will often drop the ${Q,S}$ and just write ${\Gamma(a,b)}$ when there can be no confusion. Let ${Q_{\text{max}}}$ be the maximum of the ${q_{i}}$‘s.

Theorem: Let ${Q}$ and ${S}$ be as above, and let ${\epsilon>0}$ and ${0 < \delta_{1} < \delta_{2} < 1}$. Then, there is an algorithm that runs in time ${\mathsf{poly}(Q_{\text{max}},m,\frac{1}{\delta_{1}},\frac{1}{\epsilon})}$. The algorithm operates as follows:

1. If ${\Gamma(\delta_{1},\delta_{2})}$ is nonempty, then the algorithm returns an element of this set;
2. If ${\Gamma(\delta_{1}-\epsilon,\delta_{2}+\epsilon)}$ is empty, then the algorithm returns “none”.

Note, the algorithm essentially finds an ${X}$ 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,

$\displaystyle X \equiv a_{i} \bmod q_{i} \ \ \ \ \ (3)$

where ${i=1,\dots,m}$. For each ${i}$ there is a ${0 < q'_{i} < q_{i}}$ so that ${ q'_{i}\Pi(Q)/q_{i} \equiv 1 \bmod q_{i}}$. This follows since each ${\Pi(Q)/q_{i}}$ is relatively prime to ${q_{i}}$. Define,

$\displaystyle Y = \sum_{i=1}^{m} a_{i}q'_{i}\Pi(Q)/q_{i}.$

The claim is that ${Y}$ is a non-negative solution to all the equations (3). This follows since ${Y \bmod q_{k}}$ is equal to

$\displaystyle \sum_{i \neq k} a_{i}q'_{i}\Pi(Q)/q_{i} + a_{k}q'_{k}\Pi(Q)/q_{k}$

which is congruent to ${a_{k}}$ modulo ${q_{k}}$: the first sum’s terms are all ${0}$ modulo ${q_{k}.}$

Note, ${Y}$ need not be less than ${\Pi(Q)}$, but for some ${t}$,

$\displaystyle X = Y -t \cdot \Pi(Q)$

is in ${[0,\Pi(Q)]}$. The question that we need to understand is: when is this ${X}$ in the range ${[0,\delta \cdot \Pi(Q)]}$? The key is the following simple lemma: (${\{z\}}$ denotes the fractional part of ${z}$)

Lemma: There is a solution ${X}$ to the equations (3) in the range ${[0,\delta \cdot \Pi(Q)]}$ if and only if

$\displaystyle \left \{ \sum_{i=1}^{m} a_{i}q'_{i}/q_{i} \right \} \le \delta \ \ \ \ \ (4)$

Proof: First, assume that (3) has a solution ${X}$ in the given range. Then, we must show that (4) is true. Clearly, for some non-negative ${t}$, ${X = Y -t \cdot \Pi(Q)}$. This follows by the CRT uniqueness and that ${Y \ge 0}$. Then, it follows that

$\displaystyle 0 \le \sum_{i=1}^{m} a_{i}q'_{i}/q_{i} -t \le \delta.$

The sum is clearly equal to ${\alpha + k}$ where ${0 \le \alpha < 1}$ and ${k \ge 0}$ is a natural number. I claim that ${k=t}$. If this is true (4) will clearly follow, since ${\alpha}$ is just the fractional part of the sum. We know that

$\displaystyle 0 \le \alpha + k -t \le \delta.$

Thus, if ${k>t}$, then the last inequality would be false; and if ${k, 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

$\displaystyle \left \{ \sum_{i=1}^{m} a_{i}q'_{i}/q_{i} \right \} \le \delta$

which implies that ${0 \le \alpha +k \le \delta}$ where again ${\alpha + k}$ is value of the sum. Further as before ${0 \le \alpha <1}$ and ${k \ge 0}$ is a natural number. But, clearly ${\alpha \le \delta}$ by the assumption. I now claim that

$\displaystyle X = Y -k \cdot \Pi(Q)$

is a solution to all the congruences and that ${X}$ satisfies the required inequalities. The first is easy, so let’s turn to the inequalities. Again ${X/\Pi(Q)}$ is equal to

$\displaystyle \sum_{i=1}^{m} a_{i}q'_{i}/q_{i} - k.$

But, this is just ${\alpha}$ by definition. Thus, ${0 \le X/\Pi(Q) = \alpha \le \delta}$, and we are done. $\Box$

The Algorithm

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

$\displaystyle x_{1}x_{2}\dots x_{m}$

where each ${x_{i}}$ is at most ${l = \log Q_{\text{max}}}$ bits. The automaton reads each input and does two things. First, it checks that ${x_{i}}$ is in the current set ${S_{i}}$. Second, it will compute the fractional part of

$\displaystyle \sum_{i=1}^{m} x_{i}q'_{i}/q_{i}.$

The first is easy and only uses order ${ |S_{1}| + \cdots + |S_{m}| }$ 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 ${\delta}$.

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 ${\delta}$ 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 ${X}$. Let ${X}$ correspond to

$\displaystyle x_{1}x_{2}\dots x_{m}.$

Then, we can also add the constraint that ${f(x_{1},\dots,x_{m}) = 1}$ 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 ${1}$‘s in each ${x_{i}}$, or that no ${x_{i} = x_{i+1}}$.

1. August 2, 2009 9:27 pm

I like this, and it seems like a neat use of BDDs. In my taste the Lemma would benefit from a shorter & more direct proof. Aside from the math, I didn’t understand
“If those who do identity theft were able to obtain the right number theory secrets, for example, we would have a potential disaster”
Here’s one thing I could imagine you were thinking: that most cryptosystems rely on “generally accepted” unproven facts, and that it would be bad if they were to find a proof that these facts are false?
Also, I think and hope math is a good example (in principle) of something which is kind of un-dominable by any subset of humanity…

2. September 2, 2009 6:03 pm

Super post, Need to mark it on Digg
Thank you

3. June 25, 2012 10:31 pm