Chinese Remainder Theorem - Applications

Applications

• In the RSA algorithm calculations are made modulo n, where n is a product of two large prime numbers p and q. 1,024-, 2,048- or 4,096-bit integers n are commonly used, making calculations in very time-consuming. By the Chinese remainder theorem, however, these calculations can be done in the isomorphic ring instead. Since p and q are normally of about the same size, that is about, calculations in the latter representation are much faster. Note that RSA algorithm implementations using this isomorphism are more susceptible to fault injection attacks.

• The Chinese remainder theorem may also be used to construct an elegant Gödel numbering for sequences, which is needed to prove Gödel's incompleteness theorems.

• The following example shows a connection with the classic polynomial interpolation theory. Let r complex points ("interpolation nodes") be given, together with the complex data, for all and . The general Hermite interpolation problem asks for a polynomial taking the prescribed derivatives in each node :

Introducing the polynomials

the problem may be equivalently reformulated as a system of simultaneous congruences:

By the Chinese remainder theorem in the principal ideal domain, there is a unique such polynomial with degree . A direct construction, in analogy with the above proof for the integer number case, can be performed as follows. Define the polynomials and . The partial fraction decomposition of gives r polynomials with degrees such that

so that . Then a solution of the simultaneous congruence system is given by the polynomial

and the minimal degree solution is this one reduced modulo, that is the unique with degree less than n.

• The Chinese remainder theorem can also be used in secret sharing, which consists of distributing a set of shares among a group of people who, all together (but no one alone), can recover a certain secret from the given set of shares. Each of the shares is represented in a congruence, and the solution of the system of congruences using the Chinese remainder theorem is the secret to be recovered. 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 Good-Thomas fast Fourier transform algorithm exploits a re-indexing of the data based on the Chinese remainder theorem. The Prime-factor FFT algorithm contains an implementation.

• Dedekind's theorem on the linear independence of characters states (in one of its most general forms) that if M is a monoid and k is an integral domain, then any finite family of distinct monoid homomorphisms (where the monoid structure on k is given by multiplication) is linearly independent; i.e., every family of elements satisfying must be equal to the family .

Proof using the Chinese Remainder Theorem: First, assume that k is a field (otherwise, replace the integral domain k by its quotient field, and nothing will change). We can linearly extend the monoid homomorphisms to k-algebra homomorphisms, where is the monoid ring of M over k. Then, the condition yields by linearity. Now, we notice that if are two elements of the index set I, then the two k-linear maps and are not proportional to each other (because if they were, then and would also be proportional to each other, and thus equal to each other since (since and are monoid homomorphisms), contradicting the assumption that they be distinct). Hence, their kernels and are distinct. Now, is a maximal ideal of for every (since is a field), and the ideals and are coprime whenever (since they are distinct and maximal). The Chinese Remainder Theorem (for general rings) thus yields that the map

given by

for all

is an isomorphism, where . Consequently, the map

given by

for all

is surjective. Under the isomorphisms, this map corresponds to the map

given by

for every

Now, yields for every vector in the image of the map . Since is surjective, this means that for every vector . Consequently, QED.