Chinese remainder theorem
Both names of the theorem refer to its earliest known statement that appeared in Sunzi Suanjing, a Chinese manuscript written during the 3rd to 5th century CE.
The Chinese remainder theorem (expressed in terms of congruences) is true over every principal ideal domain.
[5] Special cases of the Chinese remainder theorem were also known to Brahmagupta (7th century) and appear in Fibonacci's Liber Abaci (1202).
[6] The result was later generalized with a complete solution called Da-yan-shu (大衍術) in Qin Jiushao's 1247 Mathematical Treatise in Nine Sections [7] which was translated into English in early 19th century by British missionary Alexander Wylie.
[10] Gauss illustrates the Chinese remainder theorem on a problem involving calendars, namely, "to find the years that have a certain period number with respect to the solar and lunar cycle and the Roman indiction.
"[11] Gauss introduces a procedure for solving the problem that had already been used by Leonhard Euler but was in fact an ancient method that had appeared several times.
This is widely used, under the name multi-modular computation, for linear algebra over the integers or the rational numbers.
The theorem can also be restated in the language of combinatorics as the fact that the infinite arithmetic progressions of integers form a Helly family.
As the ni are pairwise coprime, their product N also divides x − y, and thus x and y are congruent modulo N. If x and y are supposed to be non-negative and less than N (as in the first statement of the theorem), then their difference may be a multiple of N only if x = y.
However, such a direct construction involves more computation with large numbers, which makes it less efficient and less used.
Nevertheless, Lagrange interpolation is a special case of this construction, applied to polynomials instead of integers.
It is easy to check whether a value of x is a solution: it suffices to compute the remainder of the Euclidean division of x by each ni.
For the simple example considered here, 40 integers (including 0) have to be checked for finding the solution, which is 39.
This implies that the solution belongs to the arithmetic progression By testing the values of these numbers modulo
This gives This method works well for hand-written computation with a product of moduli that is not too big.
Although dramatically faster than the systematic search, this method also has an exponential time complexity and is therefore not used on computers.
Iterating this process provides eventually the solution with a complexity, which is quadratic in the number of digits of the product of all moduli.
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.
The univariate polynomials over a field is the typical example of a Euclidean domain which is not the integers.
However, the latter construction may be simplified by using, as follows, partial fraction decomposition instead of the extended Euclidean algorithm.
This solution is A special case of Chinese remainder theorem for polynomials is Lagrange interpolation.
Both Lagrange interpolation and Chinese remainder theorem assert the existence of a unique polynomial
is In fact, reducing the right-hand side to a common denominator one gets and the numerator is equal to one, as being a polynomial of degree less than
, then the solution is given by This defines an integer, as g divides both m and n. Otherwise, the proof is very similar to that for coprime moduli.
Most implementations of RSA use the Chinese remainder theorem during signing of HTTPS certificates and during decryption.
Secret sharing using the Chinese remainder theorem uses, along with the Chinese remainder theorem, special sequences of integers that guarantee the impossibility of recovering the secret from a set of shares with less than a certain cardinality.
The range ambiguity resolution techniques used with medium pulse repetition frequency radar can be seen as a special case of the Chinese remainder theorem.
of finite abelian groups, we can use the Chinese remainder theorem to give a complete description of any such map.
These observations are pivotal for constructing the ring of profinite integers, which is given as an inverse limit of all such maps.
The Chinese Remainder Theorem (for general rings) yields an isomorphism: where Consequently, the map is surjective.
