# Analog to the Chinese Remainder Theorem in groups other than Z_n.

The idea hit me when I was in my Elliptic Curve Cryptography class. $Z_n \leftrightarrow Z_{f_1} \times Z_{f_2} \times ...$ where $f_1 \times f_2 \times ... = n$ and $\{f_1, f_2, ...\}$ are pairwise coprime. Applications of this Chinese Remainder Theorem not only include computational speedups (in the case of decryption in RSA) but also stronger cryptographic attacks against $Z_n$ (for example, Pollard Rho factoring exploits this structure). Can we extend these applications into other areas? (Admittedly I don't know many computationaly examples where this could be useful, but can imagine that Mathematica/Maple would find some uses).

So the real question: is this property just a "coincidence" or are there analogs in other groups? If there are, is there some group theory analog that applies equally well to every group? If there are not, what underlying structure in the natural numbers makes this possible?

-
Come on, this is on wikipedia. –  Harry Gindi Mar 21 '10 at 3:25
en.wikipedia.org/wiki/… –  Harry Gindi Mar 21 '10 at 3:26
@IP: I couldn't really parse the cryptographic part of the question (although I admittedly know very little cryptography), so I just answered the "real question" in the second paragraph. If the OP is looking for a cryptographic answer, then I think some clarification is needed. –  Pete L. Clark Mar 21 '10 at 5:13
The question is poor, but I don't think it should be closed. As Pete says, if OP wants a cryptography answer, that needs clarification. But a number of answerers have successfully reinterpreted the question as one that's interesting mathematically, and for that they should get credit. –  Theo Johnson-Freyd Mar 21 '10 at 5:20
Closing the question doesn't prevent people from voting on answers... –  Harry Gindi Mar 21 '10 at 5:53

The Chinese Remainder theorem is usually thought of as an isomorphism of rings, not just of cyclic groups. In this regard it has a vast generalization:

Theorem (Ideal-theoretic CRT): Let R be a commutative ring, and let $I_1,\ldots,I_n$ be a finite set of ideals in $R$ which are pairwise comaximal: for all $i \neq j$, $I_i + I_j = R$. Then $I_1 \cap \ldots \cap I_n = I_1 \cdots I_n$ and the natural homomorphism

$R/I_1 \cdots I_n = R/I_1 \cap \ldots \cap I_n \rightarrow \bigoplus_{i=1}^n R/I_i$

is an isomorphism. (See e.g. Theorem 41 on p.31 of http://math.uga.edu/~pete/integral.pdf.)

One could also think of $\mathbb{Z}/n\mathbb{Z}$ as a $\mathbb{Z}$-module, and then the CRT decomposition is a special case of primary decomposition for $R$-modules. In general rings, primary decomposition is somewhat complicated (e.g. it need not be unique), but for finitely generated torsion modules over a PID there is a straightforward analogue.

Finally, thinking about it in terms of groups, CRT has the following generalization: a finite group is nilpotent iff each Sylow $p$-subgroup is normal and $G$ is the direct product of its Sylow $p$-subgroups. There are Sylow decompositions in certain other group-theoretic contexts as well, e.g. nilpotent profinite groups.

-
Pete, there's a typo at the end of the first sentence of the statement of the Theorem. –  Tom Leinster Mar 21 '10 at 2:38
Thanks, Tom. You or anyone else can certainly feel free to correct typos in my answers if you feel like it -- I would view it as your doing me a favor. –  Pete L. Clark Mar 21 '10 at 2:41
+1 for the last part, which was interesting (and not on Wikipedia). –  Harry Gindi Mar 21 '10 at 3:27
I am wondering: does the module version of the CRT (Under the same conditions as the ideal-theoretic CRT in the above post, if $A$ is an $R$-module, then the natural homomorphism $A/I_1\cdots I_nA = A/I_1A\cap\cdots \cap I_nA\to \bigoplus_{i=1}^{n} A/I_iA$ is an isomorphism of $R$-modules) directly follow from the above ring-only version (which is its particular case when $R=A$)? Because if not, I think it is the "real" generalization of the CRT, and the ring-only version should be considered a particular case. At least, I have used the module version more often than the ring-only one. –  darij grinberg Mar 21 '10 at 20:57
Okay, I guess the module version follows from the ring-only version by applying the latter to the ring $R\oplus A$ (where multiplication inside $R\oplus 0$ is inherited from $R$, multiplication between $R\oplus 0$ and $0\oplus A$ is given by the $R$-module structure on $A$, and multiplication inside $0\oplus A$ is defined as identically zero), but this is quite artificial. I am wondering whether there is a simpler approach. –  darij grinberg Mar 21 '10 at 21:00

Here is a variation on CRT for unit groups in modular arithmetic when the two moduli $m$ and $n$ may not be relatively prime: the natural reduction/diagonal map $(\mathbf Z/mn\mathbf Z)^\times \rightarrow (\mathbf Z/m\mathbf Z)^\times \times (\mathbf Z/n\mathbf Z)^\times$ need not be an isomorphism, but it always fits into an exact sequence $$1 \rightarrow K \rightarrow (\mathbf Z/mn\mathbf Z)^\times \rightarrow (\mathbf Z/m\mathbf Z)^\times \times (\mathbf Z/n\mathbf Z)^\times \rightarrow (\mathbf Z/d\mathbf Z)^\times \rightarrow 1,$$ where $K$ is all $a \bmod mn$ such that $a \equiv 1 \bmod \text{lcm}(m,n)$ and $d = \gcd(m,n)$, with the map to $(\mathbf Z/d\mathbf Z)^\times$ being given by $(u,v) \mapsto uv^{-1}\bmod d$. (All this is really doing is making the cokernel explicit as a unit group.) Note $K$ has size $\text{lcm}(m,n)/mn = \gcd(m,n) = d$.

Taking the alternating product of the sizes of these groups, we get $$\frac{d \cdot \varphi(m)\varphi(n)}{\varphi(mn)\cdot \varphi(d)} = 1 \Longrightarrow \varphi(mn) = \varphi(m)\varphi(n)\frac{d}{\varphi(d)},$$ which is a formula for $\varphi(mn)$ even if $m$ and $n$ are not relatively prime. Of course this last formula can be derived directly from manipulations with Euler's formula $\varphi(N) = N\prod_{p|N} (1 - 1/p)$ when $N = m$, $n$, and $mn$, but that makes it seem kind of accidental. Is such a formula for $\varphi(mn)$ in case $\gcd(m,n) \not= 1$ of any use at all? I know two applications: a proof that if $\mathbf Q(\zeta_m) = \mathbf Q(\zeta_n)$ then $m = n$ or one of $m$ and $n$ is odd and the other number is its double (like $\mathbf Q(\zeta_5)= \mathbf Q(\zeta_{10})$ since $-\zeta_5$ has order 10) and a proof that $\mathbf Q(\zeta_m) \cap \mathbf Q(\zeta_n) = \mathbf Q(\zeta_{(m,n)})$.

-
This is really interesting. It's a shame I can't accept two answers. –  Ross Snider Mar 21 '10 at 16:40

What you know as the Chinese remainder theorem for the abelian group $\mathbb{Z}/n\mathbb{Z}$ (which you probably don't want to call a simple group" unless $n$ is prime, as this term has a technical meaning that doesn't apply to composite $n$) is a special case of a general result in basic ring theory that can be found in any introductory text on algebra (for instance, the text of Hungerford, where the result without requiring the ring to have an identity, so there's a bizarre extra hypothesis, or Dummit and Foote, where it is stated in its usual form). The result is especially useful in the theory of Dedekind domains, which can be thought of as a generalization of the ring of integers.

I have a feeling people are going to cite this question as being somewhat inappropriate for the site, as it isn't research level, but I figured I'd attempt to steer you in the right direction anyway.

-
Thanks, I removed "simple" from the question. I figured this was legit and interesting enough for research mathematicians, but I could be mistaken. If I am, I apologize in advance. –  Ross Snider Mar 21 '10 at 2:03

Apart from the Chinese Remainder Theorem for rings, modules cited by the others, there actually also is a much more general version (for groups it seems to give something different from Pete's Sylow group version):

There is a version of the Chinese Remainder Theorem which is valid for general algebraic structures, after a suitable reformulation: An algebra is a set $M$ with some $n$-ary operations $f:M^n \rightarrow M$ (for varying $n$), possibly required to satisfy some equations between them. A homomorphism is a map preserving these operations, a congruence relation is a binary relation $R \subseteq M \times M$ which is of the form {$(x,y)|g(x)=g(y)$}$=:Ker\ g$ for some homomorphism $g$.

In the special case of ring theory these notions would be rings, ring homomorphisms and the relations {$(x,y)|x-y \in I$} for ideals $I$. As in ring theory, congruence relations are equivalence relations and the quotient set carries an algebra structure of the same kind as the original set, given by applying the old operations to equivalence classes. Intersection of congruence relations is a congruence relation again. One also can define products of algebras in the obvious way and it still is true that a homomorphism has an inverse homomorphism iff it is bijective.

Now the Chinese Remainder Theorem says:

Given algebras $A$ and $A_i \ (i \in I)$ and homomorphisms $f_i:A \rightarrow A_i$, then $f:A \rightarrow \Pi_{i \in I} A_i$ is injective if and only if $\bigcap_{i \in I}Ker\ f_i=\Delta_A$, the diagonal, i.e. the minimal congruence relation.

To see how this contains the Chinese Remainder Theorem as you know it, consider the maps $f_i:A \rightarrow A_i=A/I_i$ to be quotient maps by congruence relations (for rings: ideals). Assume that the map into the product is surjective (for rings this is the same as saying that the ideals are coprime). The kernel of the map $f$ into the product is the intersection of the individual kernels. Thus $f$ factors through $\bar{f}:A/\cap Ker\ f_i \rightarrow \Pi_{i \in I}A_i$ where $\bar{f}$ is of course still surjective. Now apply the theorem to $\bar{f}$; as we already factored out the intersection of the original kernels, the intersection of the kernels in the quotient algebra is the diagonal. So $\bar{f}$ is injective and thus an isomorphism.

You can read about this general setup in the book "Universal Algebra" by Burris and Sankappanavar, freely available here. The Chinese Remainder Theorem is Theorem 7.15 there.

-
Is this truly a generalization of the ring-theoretic CRT? It seems to say only that the CRT homomorphism is injective, which is the obvious part of the theorem. The meat of it is to prove the surjectivity. Also, does this universal algebra result have "mainstream" applications? –  Pete L. Clark Mar 21 '10 at 4:27
Hm, now that I think about it I agree - the main statement of the CRT for rings is probably that the ideals being coprime implies that the product map is surjective. The rest is the general nonsense I exposed above. I don't know of any application of this, nor of any other part of Universal Algebra, other than not having to think again about such things for each new algebraic structure. I appreciated to see the scope of validity of these principles, though. –  Peter Arndt Mar 21 '10 at 4:53

I did a course titled something similar in my undergraduate, and while it didn't teach the following applications, H. Cohen's A Course in Computational Algebraic Number Theory (which I read right after the course, and you should too) does.

As you mention, one can use the Pollard rho algorithm to find a factor $p$ of $N$, in time $O(\sqrt p)$. There are two other basic algorithms that use CRT implicitly, both in Cohen's book:

1) Pollard's $p-1$ (and its generalizations, such as Williams' $p+1$): Compute $gcd(a^{n!}-1, N)$. If $p-1 | n!$, then the gcd will be divisible by $p$, and one can factor. This uses CRT implicitly in the following way: we can compute the $gcd(a^{n!}-1,N)$ using only mod-$N$ operations - but we find $p$ because of the existence of CRT. If we accidently get $N$ as the gcd, we can still factor using another application of CRT. Read the above referenced book for details.

2) The much faster Elliptic Curve Method: Initialize an "elliptic curve" $E$ mod $N$ and a point $P$ on it. Compute $(n!)P$. I write "elliptic curve" because we aren't really defining an elliptic curve - $\mathbb{Z}/(N)$ is not a field! But, using CRT, we treat it as the combination fields. We hope that the order of $P$ on $E/\mathbb{F}_p$ divides $n!$, and mod any other prime dividing $N$, the order does not divide $n!$. In this case $(n!)P$ will "have" $p$ in its denominator, but not the other primes, allowing us to recover $p$. This, again, is using CRT much in the same way that Pollard's Rho does. We compute things only mod $N$ - but we get things that are structurely inherit, such as $p$.

3) A bit of a different kind of computational application of CRT is D. J. Bernstein's "Doubly focused enumeration of locally square polynomial values." (Pages 69--76 in High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, edited by Alf van der Poorten, Andreas Stein. Fields Institute Communications 41, American Mathematical Society, 2004. ISBN 0-8218-3353-7).

The author uses CRT explicitly in order to enumerate over numbers satisfying certain congruence properties. It is not cryptographic, but computationally interesting and simple to understand, not to mention record braking.

-