Editing Chinese remainder theorem (section)

==Computation==
Consider a system of congruences:
:<math>\begin{align} 
 x &\equiv a_1  \pmod{n_1} \\
 &\vdots             \\ 
 x &\equiv a_k \pmod{n_k}, \\ 
\end{align}</math>
where the <math>n_i</math> are [[pairwise coprime]], and let <math>N=n_1 n_2\cdots n_k.</math> In this section several methods are described for computing the unique solution for <math>x</math>, such that <math>0\le x<N,</math> and these methods are applied on the example
:<math>
\begin{align}
 x &\equiv 0 \pmod 3 \\
 x &\equiv 3 \pmod 4 \\
 x &\equiv 4 \pmod 5.
\end{align}
</math>

Several methods of computation are presented. The two first ones are useful for small examples, but become very inefficient when the product <math>n_1\cdots n_k</math> is large. The third one uses the existence proof given in {{slink||Existence (constructive proof)}}. It is the most convenient when the product <math>n_1\cdots n_k</math> is large, or for computer computation.

===Systematic search===
It is easy to check whether a value of {{mvar|x}} is a solution: it suffices to compute the remainder of the [[Euclidean division]] of {{mvar|x}} by each {{math|''n''<sub>''i''</sub>}}. Thus, to find the solution, it suffices to check successively the integers from {{math|0}} to {{mvar|N}} until finding the solution.

Although very simple, this method is very inefficient. For the simple example considered here, {{math|40}} integers (including {{math|0}}) have to be checked for finding the solution, which is {{math|39}}. This is an [[exponential time]] algorithm, as the size of the input is, up to a constant factor, the number of digits of {{mvar|N}}, and the average number of operations is of the order of {{mvar|N}}.

Therefore, this method is rarely used, neither for hand-written computation nor on computers.

===Search by sieving===
[[File:Chinese_remainder_theorem_sieve.svg|thumb|The smallest two solutions, 23 and 128, of the original formulation of the Chinese remainder theorem problem found using a sieve]]
The search of the solution may be made dramatically faster by sieving. For this method, we suppose, without loss of generality, that <math>0\le a_i <n_i</math> (if it were not the case, it would suffice to replace each <math>a_i</math> by the remainder of its division by <math>n_i</math>). This implies that the solution belongs to the [[arithmetic progression]]
:<math>a_1, a_1 + n_1, a_1+2n_1, \ldots</math>
By testing the values of these numbers modulo <math>n_2,</math> one eventually finds a solution <math>x_2</math> of the two first congruences. Then the solution belongs to the arithmetic progression 
:<math>x_2, x_2 + n_1n_2, x_2+2n_1n_2, \ldots</math>
Testing the values of these numbers modulo <math>n_3,</math> and continuing until every modulus has been tested eventually yields the solution.

This method is faster if the moduli have been ordered by decreasing value, that is if <math>n_1>n_2> \cdots > n_k.</math> For the example, this gives the following computation. We consider first the numbers that are congruent to 4 modulo 5 (the largest modulus), which are 4, {{nowrap|1=9 = 4 + 5}}, {{nowrap|1=14 = 9 + 5}}, ... For each of them, compute the remainder by 4 (the second largest modulus) until getting a number congruent to 3 modulo 4. Then one can proceed  by adding {{nowrap|1=20 = 5&thinsp;×&thinsp;4}} at each step, and computing only the remainders by 3. This gives
:4 mod 4 → 0. Continue
:4 + 5 = 9 mod 4 →1.  Continue
:9 + 5 = 14 mod 4 → 2. Continue
:14 + 5 = 19 mod 4 → 3. OK, continue by considering remainders modulo 3 and adding 5&thinsp;×&thinsp;4 = 20 each time
:19 mod 3 → 1. Continue
:19 + 20 = 39 mod 3 → 0. OK, this is the result.

This method works well for hand-written computation with a product of moduli that is not too big. However, it is much slower than other methods, for very large products of moduli. Although dramatically faster than the systematic search, this method also has an [[exponential time]] complexity and is therefore not used on computers.

===Using the existence construction===
The [[#Existence (constructive proof)|constructive existence proof]] shows that, in the [[#Case of two moduli|case of two moduli]], the solution may be obtained by the computation of the [[Bézout coefficients]] of the moduli, followed by a few multiplications, additions and [[modulo operation|reductions modulo <math>n_1n_2</math>]] (for getting a result in the [[interval (mathematics)|interval]] <math>(0, n_1n_2-1)</math>). As the Bézout's coefficients may be computed with the [[extended Euclidean algorithm]], the whole computation, at most, has a [[quadratic time]] [[time complexity|complexity]] of <math>O((s_1+s_2)^2),</math> where <math>s_i</math> denotes the number of digits of <math>n_i.</math>

For more than two moduli, the method for two moduli allows the replacement of any two congruences by a single congruence modulo the product of the moduli. Iterating this process provides eventually the solution with a complexity, which is quadratic in the number of digits of the product of all moduli. This quadratic time complexity does not depend on the order in which the moduli are regrouped. One may regroup the two first moduli, then regroup the resulting modulus with the next one, and so on. This strategy is the easiest to implement, but it also requires more computation involving large numbers.

Another strategy consists in partitioning the moduli in pairs whose product have comparable sizes (as much as possible), applying, in parallel, the method of two moduli to each pair, and iterating with a number of moduli approximatively divided by two. This method allows an easy parallelization of the algorithm. Also, if fast algorithms (that is, algorithms working in [[quasilinear time]]) are used for the basic operations, this method provides an algorithm for the whole computation that works in quasilinear time.

On the current example (which has only three moduli), both strategies are identical and work as follows.

[[Bézout's identity]] for 3 and 4 is
:<math>1\times 4 + (-1)\times 3 = 1.</math>
Putting this in the formula given for proving the existence gives 
:<math>0\times 1\times 4 + 3\times (-1)\times 3 =-9</math>
for a solution of the two first congruences, the other solutions being obtained by adding to −9 any multiple of {{nowrap|1=3&thinsp;×&thinsp;4 = 12}}. One may continue with any of these solutions, but the solution {{nowrap|1=3 = −9 +12}} is smaller (in [[absolute value]]) and thus leads probably to an easier computation

Bézout identity for 5 and 3&thinsp;×&thinsp;4 = 12 is
:<math>5\times 5 +(-2)\times 12 =1.</math>
Applying the same formula again, we get a solution of the problem:
:<math>5\times 5 \times 3 + 12\times (-2)\times 4 = -21.</math>
The other solutions are obtained by adding any multiple of {{nowrap|1=3&thinsp;×&thinsp;4&thinsp;×&thinsp;5 = 60}}, and the smallest positive solution is {{nowrap|1=−21 + 60 = 39}}.

===As a linear Diophantine system===
The system of congruences solved by the Chinese remainder theorem may be rewritten as a [[Diophantine equation#System of linear Diophantine equations|system of linear Diophantine equation]]s:
:<math>\begin{align} 
 x &= a_1 +x_1n_1\\ 
 &\vdots   \\ 
 x &=a_k+x_kn_k, 
\end{align}</math>
where the unknown integers are <math>x</math> and the <math>x_i.</math> Therefore, every general method for solving such systems may be used for finding the solution of Chinese remainder theorem, such as the reduction of the [[matrix (mathematics)|matrix]] of the system to [[Smith normal form]] or [[Hermite normal form]]. However, as usual when using a general algorithm for a more specific problem, this approach is less efficient than the method of the preceding section, based on a direct use of [[Bézout's identity]].