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

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

2010-03-21T01:49:19Z

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?

Answer by Keenan Kidwell for Analog to the Chinese Remainder Theorem in groups other than Z_n.

2010-03-21T01:58:51Z

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.

Answer by Pete L. Clark for Analog to the Chinese Remainder Theorem in groups other than Z_n.

2010-03-21T02:34:24Z

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.

Answer by Peter Arndt for Analog to the Chinese Remainder Theorem in groups other than Z_n.

2010-03-21T04:14:02Z

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.

Answer by KConrad for Analog to the Chinese Remainder Theorem in groups other than Z_n.

2010-03-21T05:25:50Z

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)})$.

Answer by Dror Speiser for Analog to the Chinese Remainder Theorem in groups other than Z_n.

2010-03-21T15:47:24Z

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.