81
$\begingroup$

As the title suggests I am interested in CRT applications. Wikipedia article on CRT lists some of the well known applications (e.g. used in the RSA algorithm, used to construct an elegant Gödel numbering for sequences...)

Do you know some other (maybe not so well known) applications? Or interesting problems (recreational? or from mathematical competitions like IMO?) which can be solved using CRT. Or any good references or examples in that direction.

I hope that with this I will have better understanding of CRT and how to use it in general.

$\endgroup$
2
  • 4
    $\begingroup$ The Chinese remainder theorem is best learned in the generality of ring theory. That is, for coprime ideals a1,...,an of a ring R, R/a is isomorphic to the product of the rings R/ai where a is defined to be the product (and by coprimality also the intersection) of the ideals ai $\endgroup$ Dec 29, 2009 at 10:43
  • 3
    $\begingroup$ Some months later: an outstanding list of applications! For those who are fond of wikipedia, I think it could provide nice hints to expand the section "Applications" in the wiki article linked in the question. $\endgroup$ Jul 30, 2010 at 10:25

30 Answers 30

72
$\begingroup$

Parallel computation: Suppose you have a huge computation to do that involves adding, multiplying and subtracting integers. Possibly also dividing but, if so, only division by numbers in a finite set S which you already know.

Choose primes $p_1$, $p_2$, ..., $p_r$ which do not divide any element of $S$, and such that $p_1 p_2 \cdots p_r$ is surely larger than your answer. Split your computation over $r$ processors, the $i$th of which computes the answer modulo $p_i$. Use CRT to put your answer back together in the end.

This was the method used in the recent computation of the Kazhdan-Lustig-Vogan polynomials of E8.

$\endgroup$
4
  • 4
    $\begingroup$ I was just about to add the computation of the character table of E8 to the list when I saw this answer. So instead, a belated +1. $\endgroup$ Jul 31, 2010 at 12:09
  • 32
    $\begingroup$ Dirk Kinnaes and I used this method to find that there are 284473580014525286666121752496600242239281330559895142380815894680093529086840703279353601839695794392738788556778405044037630360510510198592329618381688979038688482537860239885961238887812656969372196798484462132843557299991075493007550627926803688745250953668796106910118867088442300850000 binary matrices of order 34 such that each row and each column have 17 ones. However I did meet one computer-illiterate mathematician who believed me when I claimed that we counted them one at a time. $\endgroup$ Jul 12, 2012 at 11:52
  • 6
    $\begingroup$ Actually the mentioned $E_8$ computations were done in serial, not in parallel. The constraint was memory, not time: the CRT allowed $1$-byte coefficients to be used instead of $4$-byte integers, which given the huge amount of coefficients required was a crucial memory savings at the time. $\endgroup$ Oct 7, 2013 at 12:41
  • $\begingroup$ How can you divide by the elements in S? I assume you meant multiplication by modular inverse, which isn't actually division, unless it happens to divide exactly. $\endgroup$
    – Realz Slaw
    Mar 5, 2014 at 17:03
58
$\begingroup$

Secret sharing. Suppose we have $N$ people. We want any $k+1$ of them to be able to launch a missile attack, but no $k$ of them to have this power.

Solution: Choose some large prime $p$ and a random polynomial $f(t)$ of degree $k$ with coefficients in $\mathbb{Z}/p$. Tell person $1$ the value of $f(1)$, person $2$ the value of $f(2)$ and so forth. (Also, everyone knows what $p$ is.) Set up the missiles to only launch when $f(0)$ is input. Any $k+1$ people can use the Chinese remainder theorem to compute $f$, and hence $f(0)$; any $k$ people do not have enough data to constrain $f(0)$ in any way.

$\endgroup$
10
  • 1
    $\begingroup$ This may be a dumb comment, but... Why not do the following instead? Choose a large prime $p$ and elements $a_1,a_2,...,a_{k+1}$ in $\mathbb{Z}/p$. Tell person $j$ the value of $a_j$, for each $j$. Set up the missiles to only launch when $\sum_{j=1}^{k+1}a_j$ is input. I am not sure if there is an essential difference between this and your suggestion. $\endgroup$ Aug 17, 2010 at 21:23
  • 3
    $\begingroup$ Because N is larger than k+1. $\endgroup$ Aug 17, 2010 at 21:38
  • 5
    $\begingroup$ FYI this is called Shamir secret-sharing. Am I right in thinking that the reason we work over $\mathbb{Z}/p$ is that one can sensibly talk about random polynomials (with the implicitly-chosen uniform distribution on each coefficient), and not have to specify a more-or-less arbitrary distribution if we, say, took real coefficients? $\endgroup$ Dec 2, 2010 at 13:49
  • 10
    $\begingroup$ First, I think this example shows that the Chinese Remainder Theorem for polynomials is not the same as the one for integers (which cannot be used in the above manner). But more importantly, this form of secret sharing does not depend on any CRT. The idea is just to have a point in a $d=k+1$-dimensional vector space as code, and a bunch of linear equations that this point satisfies as secrets, such that any $d$-subset of them forms a Cramer system that can be uniquely solved, while fewer than $d$ of them of course do not allow this. $\endgroup$ Oct 7, 2013 at 12:33
  • 3
    $\begingroup$ Agree with @Marc. Many of the other answers are cool but this is one is hardly more spectacular than any protocol using mere linear independence. No idea why people upvote it so much. $\endgroup$
    – Marek
    Dec 10, 2013 at 18:18
54
$\begingroup$

The Chinese remainder theorem is used to resolve multiple range ambiguities in many radar systems.

$\endgroup$
3
  • 23
    $\begingroup$ To elaborate on this, because it's more applied than the rest: Many radar systems work by sending EM pulses out at regular intervals, waiting in between pulses to look for reflections from objects. You want to calculate an object's distance from the time it takes to see a reflection. If time between pulses is very long, this works, but if you're observing something dynamic you want fast updates, so you need shorter time between pulses. But then you don't know which pulse's reflection you're seeing, so object range is only known modulo (speed of light)*(pulse interval). (cont'd) $\endgroup$
    – Ian
    Jul 30, 2010 at 2:14
  • 11
    $\begingroup$ (cont'd from above) The solution is to send out a few different types of pulses (say, with different wavelengths of light), with each type of pulse having it's own pulse interval, and making those intervals coprime. Then you can use the CRT to calculate range mod some very large distance (where you know, practically speaking, that you won't be registering any reflections from such large distances). $\endgroup$
    – Ian
    Jul 30, 2010 at 2:23
  • 7
    $\begingroup$ This is detailed on p 306 of Roger Sullivan's book Microwave radar: imaging and advanced concepts $\endgroup$ Oct 16, 2010 at 2:10
48
$\begingroup$

Lagrange interpolation is a special case of the Chinese remainder theorem. (Fixing a dead link: https://artofproblemsolving.com/community/c1157h990758_the_chinese_remainder_theorem_and_lagrange_interpolation )

The Jordan normal form can be proven extremely quickly using the Chinese remainder theorem for modules over a commutative ring. This proceeds by first proving the Jordan-Chevalley decomposition, and then the rest is a simple exercise of showing what the Jordan blocks actually look like.

The first one is very surprising to people, but if you state Lagrange interpolation correctly, it's easy to see that the idea is not only similar but identical.

$\endgroup$
7
  • 3
    $\begingroup$ This sounds interesting. Can you give a reference? $\endgroup$
    – Idoneal
    Dec 29, 2009 at 15:57
  • 3
    $\begingroup$ or elaborate on this? $\endgroup$ Dec 29, 2009 at 19:13
  • 4
    $\begingroup$ I explained the connection between CRT and Lagrange interpolation on my old blog once: artofproblemsolving.com/Forum/weblog_entry.php?t=237669 . $\endgroup$ Dec 29, 2009 at 23:07
  • 1
    $\begingroup$ That's the page I was going to link! The other thing about the JNF is standard and can be found in any algebra book, but there's an exercise in Lang's Algebra in the chapter "Representations of one endomorphism" detailing the proof of the Jordan-Chevalley decomposition of an endomorphism of a vector space over an algebraically closed field. $\endgroup$ Dec 29, 2009 at 23:18
  • 4
    $\begingroup$ Why is this comment on my answer rather than the op? $\endgroup$ Dec 30, 2009 at 15:10
35
$\begingroup$

Here are some applications I don't see listed among the other answers.

  1. Everyone knows $5^2$ ends in 5 and $6^2$ ends in 6. Your task: find multi-digit numbers whose squares end in themselves (e.g., $25^2$ ends in 25, $76^2$ ends in 76, ...). This problem can be given to students -- even children -- who know no particular mathematics and they discover experimentally for $n$ = 2, 3, 4, ... that there are usually two $n$-digit solutions (sometimes fewer than 2 solutions, but never more than 2). As for whether this pattern persists for all $n$, both that there usually are solutions and that there are at most two solutions among $n$-digit numbers, turn the problem into a congruence condition and then think about CRT.

  2. If $f(x)$ is in ${\mathbf Z}[x]$ and all of its values $f(a)$ for $a$ in ${\mathbf Z}$ are multiples of either 2 or 3, then CRT implies all of its values are multiples of 2 or all of its values are multiples of 3. On the surface, this seems kind of miraculous, doesn't it? (Same result works by CRT if you replace {2,3} with any finite set of pairwise relatively prime integers.)

  3. The Solovay-Strassen probabilistic primality test. Verifying that this test admits a witness for odd composite moduli uses CRT. When I teach undergraduate number theory, the SS test has always been the last topic in the course and it's a neat application of CRT.

  4. If $a$ is not a square in $\mathbf Z$ then there are infinitely many primes $p$ such that $a \bmod p$ is not a square. This is an application of the Chinese remainder theorem and quadratic reciprocity. (This can be superseded in a quantitative sense if you use Dirichlet's theorem on primes in arithmetic progression.)

  5. If $m \mid n$ then the reduction map ${\mathbf Z}/n{\mathbf Z} \rightarrow {\mathbf Z}/m{\mathbf Z}$ is easily surjective. Please try to prove by elementary methods that the reduction map on units, $({\mathbf Z}/n{\mathbf Z})^\times \rightarrow ({\mathbf Z}/m{\mathbf Z})^\times$, is surjective without using CRT. Using CRT it is quite easy. (You can yank in Dirichlet's theorem on primes for a fast proof, but that's a rather deep result compared to CRT, so it wouldn't count as an elementary proof avoiding CRT.)

$\endgroup$
10
  • $\begingroup$ I think you are using the symbol $\equiv$ in a nonstandard way in 2 above. $\endgroup$
    – Idoneal
    Jan 17, 2010 at 5:49
  • 2
    $\begingroup$ Huh? The notation looks correct to me. It's the congruence notation from modular arithmetic. To say a number is 0 mod m means it is a multiple of m, and that's the situation I'm describing in 2. In what way does the usage look nonstandard? (I said at the start that a runs over integers, and that remains true anywhere later on as well.) $\endgroup$
    – KConrad
    Jan 17, 2010 at 6:17
  • $\begingroup$ The statement starting at "That is," in 2. is not what you meant to write, based on what you say in the first sentence. It says "If $6$ divides $f(a)$ for all $a$, then either $2$ divides every $f(a)$, or $3$ divides every $f(a)$", which is certainly true and does not use CRT. I think that's why Idoneal was suggesting that it was a modified version of congruence. You could instead say "That is, if $f(a) \equiv 0, 2, 3$, or $4 \mod{6}$ for each $a$, then either..." $\endgroup$ Jul 12, 2012 at 1:35
  • $\begingroup$ Since this is a few years old, do you know if the question on squares is still open? $\endgroup$ Jul 12, 2012 at 1:36
  • 2
    $\begingroup$ @Zack: Thanks for pointing that out. I fixed the statement of 2. And as far as I know the question on squares is still unproved. $\endgroup$
    – KConrad
    Jul 12, 2012 at 2:51
28
$\begingroup$

There are some cute exercises based on the Chinese remainder theorem, e.g.,

(1) there exist an arbitrarily large number of consecutive integers, none of which is squarefree (1955 Putnam Competition),

(2) there exist an arbitrarily large number of consecutive integers, none of which is powerful ($n$ is powerful if for every prime $p$ dividing $n$, we have $p^2 \mid n$),

(3) there exist an arbitrarily large number of consecutive positive integers, none of which is a sum of two squares,

(4) the number of integers $1\cdot 2, 2\cdot 3, \dots, n\cdot (n+1)$ divisible by $n$ is $2^{\omega(n)}$, where $\omega(n)$ is the number of distinct prime divisors of $n$.

$\endgroup$
2
  • 6
    $\begingroup$ By way of contrast to (2), I believe it is unknown whether there exist three consecutive integers each of which is powerful. $\endgroup$ Jul 12, 2012 at 6:21
  • $\begingroup$ In the same spirit, for every $n$ there exist $x$ and $y$ such that none of $\{x, \ldots, x+n\}$ is relatively prime to any of $\{y, \ldots, y+n\}$. $\endgroup$ May 30, 2019 at 5:19
21
$\begingroup$

In the proof of Gödel's First Incompleteness Theorem, you need to choose a way to encode formulas and proofs as numbers. The easy way to do this is to take 2i03i15i3...pjij. However you can instead use the Chinese Remainder Theorem to pick a number congruent to i0 mod p0, congruent to i1 mod p1, etc. (Of course, you need to pick big enough primes then.) The advantage of doing this is you no longer need exponentiation in your theory, just multiplication and addition.

$\endgroup$
1
  • 6
    $\begingroup$ I assumed that this is what was meant by "used to construct an elegant Gödel numbering for sequences" in the original question. $\endgroup$ Sep 18, 2010 at 23:03
14
$\begingroup$

Quadratic Reciprocity

Perhaps the best application of the CRT is in a proof of the Gauss' Quadratic Reciprocity, a proof due to Rousseau (my version found on my blog here) that uses just the CRT. It is very rare that proofs of the QR drop out without a lot of effort :)

$\endgroup$
2
  • 4
    $\begingroup$ It is an application of CRT, but it does not qualify as "perhaps the best". Even among proofs of quadratic reciprocity, this is not one of the nicer ones (in terms of elegance or insight). I've seen a lot of such proofs and this wouldn't go in my top 5. $\endgroup$
    – KConrad
    Jan 17, 2010 at 19:17
  • 28
    $\begingroup$ Wow, tough crowd. $\endgroup$ Jan 29, 2010 at 6:22
12
$\begingroup$

You already bring this idea up when you mention RSA but I want to make the point more generally: There are very good methods for solving polynomial equations modulo primes and prime powers. The only good way to solve an equation modulo $N$ is to factor $N$; solve modulo each prime power dividing $N$, and use Chinese remainder to put a solution back together. This is true even for computing square roots.

$\endgroup$
12
$\begingroup$

CRT combined with Dirichlet's theorem allows you to prove the existence of infinitely many primes satisfying any system of congruences that has a solution; I sketched a proof that this implies that the square roots of integers have no nontrivial linear dependences here.

$\endgroup$
12
$\begingroup$

Here is a neat example that predates David Speyer's example of fast parallel arithmetic, but uses the same trick.

Richard J. Lipton, Yechezkel Zalcstein: Word Problems Solvable in Logspace. J. ACM 24(3): 522-526 (1977)

In this paper, the Chinese remainder theorem is used to prove that the word problem on several types of groups are solvable in logspace. (The Chinese remainder theorem is not explicitly invoked, but one can use it to justify the algorithms.) For instance, the paper states:

Corollary 6. The word problem for finitely generated free groups is solvable in logspace.

The word problem for a finite group is to determine if a given product of group elements equals the identity. The results are proved by embedding a group into a group of matrices over the integers, then computing the matrix product modulo all small primes.

$\endgroup$
10
$\begingroup$

Many properties of $\mathbb{Z}/n$ can be broken down to properties of $\mathbb{Z}/p^i$ using the Chinese Remainder Theorem. Here is an example that I have no idea how to prove otherwise:

IMO Shortlist 1997 problem 15 is equivalent to proving that if some given integer is a square residue modulo $n$ and a cubic residue modulo $n$ at the same time, then it is a $6$-th power residue modulo $n$ as well. More generally, if $n$, $u$, $v$ are three positive integers, and some given $a\in\mathbb{Z}/n$ is both a $u$-th power and a $v$-th power in $\mathbb{Z}/n$, then $a$ is a $\mathrm{lcm}\left(u,v\right)$-th power in $\mathbb{Z}/n$.

$\endgroup$
10
$\begingroup$

The chinese remainder theorem can be generalized as follows: Let $G$ be a group with normal subgroups $H,K$ of $G$. Then the canonical map $G/(H \cap K) \to G/H \times_{G/(HK)} G/K$ is an isomorphism. The proof is trivial! With the same argument: Let $R$ be a ring with ideals $I,J$, then the canonical map $R/(I \cap J) \to R/I \times_{R/(I+J)} R/J$ is an isomorphism. Now this reveals a geometric meaning of the cinese remainder theorem:

Let $X$ be a scheme and $A,B$ two closed subschemes of $X$. Then $A \cup B$ is a closed subscheme of $X$ (intersect the ideal sheaves) and we have $A \cup B = A \coprod_{A \cap B} B$.

Thus the union of two closed subschemes is the pushout of $A$ and $B$ along $A \cap B$, which is very intuitive.

$\endgroup$
9
$\begingroup$

One application : to find the product of all elements in the multiplicative group $({\mathfrak o}/{\mathfrak a})^\times$, where $\mathfrak o$ is the ring of integers in a number field and ${\mathfrak a}\subset{\mathfrak o}$ is an ideal. The case ${\mathfrak o}={\mathbb Z}$ is Wilson's theorem. See for example arXiv:0711.3879v1 [math.NT].

$\endgroup$
1
9
$\begingroup$

The Chinese Remainder Theorem gives a way to compute matrix exponentials.

Indeed, let $A$ be a complex square matrix, put $B:=\mathbb C[A]$. This is a Banach algebra, and also a $\mathbb C[X]$-algebra ($X$ being an indeterminate). Let $S$ be the set of eigenvalues of $A$, $$\mu=\prod_{s\in S}\ (X-s)^{m(s)}$$ the minimal polynomial of $A$, and identify $B$ to $\mathbb C[X]/(\mu)$.

The Chinese Remainder Theorem says that the canonical $\mathbb C[X]$-algebra morphism $$\Phi:B\to C:=\prod_{s\in S}\ \mathbb C[X]/(X-s)^{m(s)}$$ is bijective.

Computing exponentials in $C$ is trivial, so the only missing piece in our puzzle is the explicit inversion of $\Phi$.

Fix $s$ in $S$ and let $e_s$ be the element of $C$ which has a one at the $s$ place and zeros elsewhere. It suffices to compute $\Phi^{-1}(e_s)$. This element will be of the form $$f=\frac{\mu}{(X-s)^{m(s)}}\ g\ \mbox{ mod }\mu$$ with $f,g\in\mathbb C[X]$, the only requirement being $$g\equiv\frac{(X-s)^{m(s)}}{\mu}\mbox{ mod }(X-s)^{m(s)}$$ (the congruence taking place in the ring of rational fractions defined at $s$). So $g$ is given by Taylor's Formula.

$\endgroup$
7
  • $\begingroup$ Isn't this just the standard recipe "Transform to the JNF, compute exponentials of Jordan blocks and transform back" ? $\endgroup$ Mar 31, 2014 at 19:45
  • $\begingroup$ @JohannesHahn - Dear Johannes: Thanks for your comment. I think it's much harder to put a matrix in JNF than to compute its exponential. I know no closed formula for the JNF. The exponential depends only on the minimal polynomial, which is a much coarser invariant than the JNF. $\endgroup$ Apr 1, 2014 at 5:31
  • 1
    $\begingroup$ @lcv - No, I don't know. All I can say is this: If $A$ is a complex square matrix and $\mu$ is its minimal polynomial, then there is a unique univariate polynomial $f$ with complex coefficients such that $\deg f<\deg\mu$ and $e^A=f(A)$. Moreover there is a simple expression for $f$ in term of the roots of $\mu$ and their multiplicities. $\endgroup$ Mar 27, 2019 at 19:14
  • 1
    $\begingroup$ @lcv - Thank you for your interest! Well, $f$ is the Lagrange interpolation polynomial iff $A$ is diagonalizable, iff the roots of $\mu$ are simple. For instance, if $A^2=0$ but $A\ne0$, then $\mu(x)=x^2,f(x)=1+x,e^A=I+A$, but Lagrange's polynomial is $g(x)=1$, which gives $g(A)=I\ne e^A$. $\endgroup$ Mar 27, 2019 at 20:55
  • 1
    $\begingroup$ Oh I see, I didn't appreciate the non-diagonalizable case. Great, so that's quite important indeed. $\endgroup$
    – lcv
    Mar 27, 2019 at 21:12
8
$\begingroup$

Here is an adorable application of the CRT in combinatorial number theory: In an exact covering system of congruences the two largest moduli must be identical. In other words, if you partition the integers into arithmetic series, then two of the series must have the same 'step size'. This is often given as an application of (basic) complex analysis but all you really need is the CRT!

http://www.emis.de/journals/EJC/Volume_8/PDF/v8i2a1.pdf

$\endgroup$
4
  • $\begingroup$ While I absolutely don't want to ruin Doron's wonderful polemic, let me add that the "complex-analytic" proof he quotes is completely algebraic. Just look at it from the correct angle: We take the equation (MNDR) and rewrite it as $\frac{1}{1-z}-\sum_{i=1}^{n-1} \frac{z^{b_i}}{1-z^{a_i}} = \frac{z^{b_n}}{1-z^{a_n}}$. Bringing the left hand side to a common denominator, this denominator is going to be a polynomial which is nonzero on any primitive $a_n$-th root of unity, so if we multiply the equation with the $a_n$-th cyclotomic polynomial, the left hand side becomes $0$. But the right ... $\endgroup$ Apr 4, 2011 at 22:56
  • 1
    $\begingroup$ ... one doesn't. $\endgroup$ Apr 4, 2011 at 22:56
  • $\begingroup$ What we DO use here is the existence of a primitive $a_n$-th root of unity. This is somewhat tricky if we wish to avoid analysis, but many books do it right. $\endgroup$ Apr 4, 2011 at 22:57
  • $\begingroup$ That's a good point! $\endgroup$ Apr 7, 2011 at 0:35
8
$\begingroup$

The Mayan calendar system uses a number of different periodic processes, and provides a simple but very important example of a practical use of the CRT.

The Tzolkin, or Day Count, has twenty weekdays (Ik, Akbal,... Auau) and thirteen numbers, 1-13. Each day, the day name advances, and so does the number. For example, 7 Ik is followed by 8 Akbal. These name/number pairs repeat in a 260 day cycle, which has been in continuous uniterrupted use since at least 600BC.

The Haab, or Vague Year, is a 365 day year consisting of 19 months (Pop, Uo, ..., Cumku, Uayeb). The first 18 months have 20 days and Uayeb has five days. The Haab runs 0 Pop, 1 Pop, ..., 19 Pop, 0 Uo, 1 Uo,..., 4 Uayeb and then repeats to 0 Pop.

Together, the Tzolkin and Haab form the calendar round, with dates given by Tzolkin then Haab, for example, 7 Ik 0 Cumku. This cycle repeats every 18980 days, about 52 years, which means that a calendar round date is good for most practical purposes (such as birth dates).

The earlier Mayan period, from around the 1st century BC to the 13th century AD, also featured a system known as the long count, recently made somewhat famous by the fact that it finished a 5126 year cycle on December 21, 2012. Long count dates have Kin (days) which run 0-19. 20 Kin make one Uinal, 18 Uinal make one Tun, 20 Tun make one Katun, and 20 Katun make one Baktun. Dates are written with Baktun first, as, for example, 9.7.17.12.14. After 13 Baktun, the date goes back to zero, so that 12.19.19.17.19 was followed by 0.0.0.0.0.

One major problem with studying the Mayan calendar is that the long count dates fell out of use hundreds of years before the Spanish arrived, and it is nontrivial to decide which Mayan long count dates correspond to which dates in the modern western calendar system - the 'correlation problem'.

The key document, the Chronicle of Oxcutzcab, says that a tun ended 13 Ahua 8 Xul in AD 1539, thus tying together the long count (tun ending), the calendar round, and the Julian calendar. From ancient records, the long count is known to have begun on 4 Ahua, 8 Cumku. So, given 0.0.0.0.0 = 4 Ahua 8 Cumku, one needs to solve $x$.0.0 = 13 Ahua 8 Xul. The day number gives the equation $360 x \equiv 9 \pmod{13}$. Since 8 Xul is 125 days after 8 Cumku, the Haab gives the second equation $360 x \equiv 125 \pmod{365}$.

So, there's a simple little use of CRT: Solve for $x$, and find $x \equiv 924 \pmod{949}$.

To finish the story, the year AD 1539 contains the long count tun 924 = 2.6.4.0.0 plus some multiple of 949 tun = 2.7.9.0.0. There is enough historical evidence to guess the date to within 949 tun (about 935 years), and so one learns that 11.16.0.0.0 is in AD 1539. Finally, the calendar round is still in use and so one can determine that 11.16.0.0.0 is November 12, 1539. I'll leave it as an exercise to determine that December 21, 2012 really was 0.0.0.0.0.

$\endgroup$
7
$\begingroup$

Pohlig–Hellman discrete logarithm computation is based on the CRT.

A degree n discrete Fourier Transform is identical to polynomial evaluation at primitive $n$-th roots of unity. The inverse transform is interpolation or the CRT (as mentioned in earlier posts).

Montgomery reduction uses the CRT to reduce an integer modulo $x\bmod{N}$ without division by $N$ by creating an integer equivalent to $x\bmod{N}$ and $0\bmod{2^r}$, then dividing by $2^r$.

$\endgroup$
7
$\begingroup$

A variant of the CRT that has many practical applications is the "explicit CRT" (see http://cr.yp.to/antiforgery/meecrt-20060914-ams.pdf, for a good introduction).

One scenario where the explicit CRT (mod m) can be used, is the following. Suppose we know the value of an integer x modulo primes p_1, ..., p_n, whose product exceeds, say, 4|x|. Now we could use a standard CRT computation to determine x, but suppose we actually wish to know x mod m, where m is some integer not among the p_i. The explicit CRT lets us compute x mod m using arithmetic operations that involve operands that are all about the same size as m (rather than x). This is useful when x >> m; if x is a 100 digit number but the p_i's and m are all 3 or 4 digits numbers, you could compute x mod m on a pocket calculator with an 8 digit display, given the values x mod p_1, ..., x mod p_n.

This technique is especially useful when one needs to compute many large integers x modulo the same m (the integers x might be the coefficients of a polynomial and m might be the characteristic of a finite field, for example). This approach is used in http://arxiv.org/abs/0903.2785 to compute Hilbert class polynomials, and in http://arxiv.org/abs/1001.0402 to compute modular polynomials, both of which are notoriously large but can be efficiently computed with the explicit CRT.

$\endgroup$
6
$\begingroup$

I often deal with combinatorial numbers $x$ are difficult to compute exactly, but it's possible to find congruences satisfied by them. You can combine the congruences using the Chinese Remainder Theorem into one concise congruence. If one day someone does compute the number $x$ by a lengthy computation, they can check that $x$ satisfies the congruence.

For instance, the number of reduced Latin squares $R_{12}$ of order $12$ is unknown, but it satisfies $R_{12} \equiv 50400 \pmod {55440}$.

$\endgroup$
6
$\begingroup$

Actually, not only the Lagrange interpolation, but more generally the Hermite interpolation problem (i.e. with prescribed jets at some nodes) may be treated as an application of the CRT. I happened to wirte some lines on it in the wiki article: http://en.wikipedia.org/wiki/Chinese_remainder_theorem#Applications (where others applications and references are also given).

$\endgroup$
6
$\begingroup$

Mark Iwen uses the CRT to construct a Sparse Fourier Transform, see:

A Deterministic Sub-linear Time Sparse Fourier Algorithm via Non-adaptive Compressed Sensing Methods, M. A. Iwen, http://arxiv.org/abs/0708.1211

$\endgroup$
6
$\begingroup$

CRT is used to generate Payam Numbers. A Payam number k can generate very prime sequences of the form k*M(x)*2^n+/-1, with n variable, M(x) a multiple of certain primes. The pursuit of very prime series using Payam numbers is a mathematical recreation currently located at

http://www.mersenneforum.org/showthread.php?t=9755

$\endgroup$
5
$\begingroup$

One application that I heard about (but haven't actually used myself) is in computing combinatorial numbers $x$ that have very many digits. Sometimes, instead of dealing with arbitrary precision arithmetic, it is easier to compute $x \pmod \mu$ for many small moduli $\mu$ (which can be substantially faster than dealing with $x$ itself) then afterwards combine the congruences using the Chinese Remainder Theorem to find $x$ itself. Although this requires that you have an upper bound on $x$ or some idea of how large it should be.

$\endgroup$
2
  • $\begingroup$ For parallel computation, see David Speyer's comment amount the Kazhdan-Lusztig-Vogan polynomials of E_8 below. $\endgroup$ Dec 29, 2009 at 22:23
  • 1
    $\begingroup$ As another example of this, I heard that people used to compute Bernoulli numbers using the von Staudt-Clausen Theorem ( en.wikipedia.org/wiki/Von_Staudt%E2%80%93Clausen_theorem ). $\endgroup$ Mar 20, 2010 at 18:29
5
$\begingroup$

Ulrich Oberst wrote an article on that in Expositiones no. 3, 1985 "Anwendungen des chinesischen Restsatzes".

$\endgroup$
5
$\begingroup$

Here’s a nice problem that was among some IMO practice problems. I don’t know the source.

Problem: Prove that for each natural number $n$, there is some natural number $r$ for which the $n$ integers $r+1^2,r+2^2,\ldots ,r+n^2$ are all squarefree.

Solution (sketch): For a large prime $p$, the probability that none of these $n$ integers is divisible by $p^2$ is $1-\frac{n}{p^2}$. Assuming independence for the $p_i$s we get $(1-\frac{n}{2^2})(1-\frac{n}{3^2})(1-\frac{n}{5^2})\ldots$, which converges to a positive number, so there must exist solutions.

To make this into a rigorous argument one needs CRT.

$\endgroup$
5
$\begingroup$

One answer I don't see here: Lagrange interpolation. If one takes, for example, the ring $\mathbb{Q}[x]$, and realizes CRT as a statement about rings and direct sums of $R/P$ over a set of co-prime $P,$ then one can construct polynomials which have cycles of arbitrary length in the rationals (or any number of cycles of arbitrary length). Lagrange interpolation has other applications, but the proof is CRT.

$\endgroup$
2
  • 1
    $\begingroup$ Way down in the second answer. $\endgroup$ Jan 29, 2010 at 5:35
  • $\begingroup$ ah! my apologies, I missed that one. $\endgroup$
    – Ben Weiss
    Jan 29, 2010 at 6:37
4
$\begingroup$

In computer science, more specifically, the theory of finite automata, the Chinese Remainder Theorem proves useful when thinking about finite automata or regular expressions over a 1-letter alphabet. The prerequisites (finite automata, regular expressions, NP-completeness) for understanding these applications are usually taught in "introduction to theoretical computer science" university courses.

For example, the universality problem for unary regular expressions is coNP-complete. The polynomial-time reduction uses chinese remaindering to encode a boolean formula into a regular expression. L. J. Stockmeyer, A. R. Meyer: Word problems requiring exponential time (Preliminary Report), Proceedings of the th annual ACM symposium on Theory of computing (STOC '73), pp. 1-9.

Also, the worst-case size blowup when moving from nondeterministic to deterministic finite automata is related to Landau's function, and the proof uses the Chinese Remainder Theorem. Marek Chrobak: Finite Automata and Unary Languages. Theoretical Computer Science 47(3): 149-158 (1986)

$\endgroup$
3
$\begingroup$

Chinese Remainder Theorem has been used in Uniswap v3 to create a 512-bit multiplication (that works for numbers below $2^{256}(2^{256} - 1)$) between 256-bit numbers, the maximum integer type in the Ethereum Virtual Machine. Here is a link for the detailed explanation: https://xn--2-umb.com/17/full-mul/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.