1
$\begingroup$

I have read a very interesting description of computation related to the RSA group as follows.

"By the Chinese remainder theorem, we have that: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^* \cong (\mathbb{Z}/(p-1)\mathbb{Z})\times (\mathbb{Z}/(q-1)\mathbb{Z})$$ From this, we should be able to write: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong \langle g_q, g_p\mid [g_q, g_p] = e, g_q^{q-1} = e, g_p^{p-1} = e\rangle$$ Where $e$ is the identity element of the group, $[g_q, g_p]$ is the commutator, etc. Essentially, this is the free abelian group on two generators, subject to the relations on the order of the generators that come from the CRT representation.

We can then write all the quantities you talk about in terms of the generators $g_q, g_p$. Say that $z = g_q^{z_q}g_p^{z_p}$, and $y = g_q^{y_q}g_p^{y_p}$. Then your equation: $$y^r = z\implies g_q^{ry_q}g_p^{ry_p} = g_q^{z_q}g_p^{z_p}\implies g_q^{ry_q - z_q}g_p^{ry_p - z_p} = e$$ Gives us the "cycle". In particular, if you view the Cayley graph as being on vertices of the form $g_q^{x}g_p^{y}$ (so we can sort of visualize it as being some subset of $\mathbb{Z}^2$), this reduces the problem of finding cycles to finding points $(y_q, y_p)$ such that $(ry_q \equiv z_q \bmod (q-1))$ and $(ry_p\equiv z_p\bmod (p-1))$. You may want to enforce some non-triviality condition (such as $ry_q\neq z_q$ and $ry_p\neq z_p$), I'm not sure. If you want to find the minimum/maximimum length cycle, you could then find the minimum/maximum non-trivial $(y_q, y_p)$ such that $ry_q \equiv z_q\bmod (q-1)$ and $ry_p\equiv z_p\bmod(p-1)$. Note that if you know the factorization of $N = pq$, you can compute $y_q \equiv r^{-1}z_q\bmod(q-1)$ and $y_p\equiv r^{-1}z_p\bmod(p-1)$ easily (assuming $r$ is invertible in both rings), and then find particular representatives $(y_p, y_q)$ with properties you want by searching through the cosets $r^{-1}z_q + (q-1)\mathbb{Z}$."

(source:Relationship between generating elements given by cycles in Cayley graph)

I have quoted it only because I was very interested in it and please don't misunderstand.

I would like to ask a few questions regarding it.

  1. For finding the maximum length cycle, it is taken as finding the maximum solution to the two congruence relations. But since these are congruent relations how can we justify that the maximum will give the answer relevant to the longest cycle?

As an example, if we consider $a \equiv 0 (modp)$ where $p$ is a prime and the solutions can take only the values $\{0,1,2,...,p\}$, then $a$ can take only the values $0$ or $p$ only. Then $ry_q$ will always be $z_q$?

a) I tried the above idea (just to check with real values easily) for a Cayley graph (undirected) of the group $\mathbb{Z}_3 \times \mathbb{Z}_5$, where the generating elements are $g_1=(0,1)$ and $g_2=(1,0)$, $|g_1|=5, |g_2|=3$. Then for a Hamiltonian cycle $g_1^{m} g_2^{n}=e$, can I write $m \equiv 0 (mod5)$ and $n \equiv 0 (mod3)$?

b) There are several Hamiltonian cycles in this graph, so when I tested it manually for one cycle it was $m=0, n=3$ and for another, it was $m=5,n=0$. Then it seems like if we solve for solutions as the maximum solution to the above equations I get several solution pairs for the combinations of $m=0,5$ and $n=0,3$. Am I right?

  1. Can we write other groups such as $(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes (\mathbb{Z}_q \times \mathbb{Z}_q)$, where $p,q$ are odd distinct primes, in terms of a free group as above? I am very glad if some guidance/steps to do so can be explained.
$\endgroup$
2
  • $\begingroup$ Dear @Mark much obliged if you can give me some help/guidance in this regard. Looking forward for your expertise guidance $\endgroup$
    – Bob Traver
    May 30, 2020 at 17:30
  • $\begingroup$ Many thanks in advance! $\endgroup$
    – Bob Traver
    May 30, 2020 at 17:30

1 Answer 1

1
$\begingroup$
  1. For finding the maximum length cycle, it is taken as finding the maximum solution to the two congruence relations. But since these are congruent relations how can we justify that the maximum will give the answer relevant to the longest cycle?

It looks like it shouldn't. I'm pretty sure I was visualizing cycles in the Cayley Graph as being paths in the lattice $\mathbb{Z}^2$. This corresponds to viewing points in the RSA group as tuples $(g_p^{r_p}, g_q^{r_q})$ (where $(r_p, r_q)\in\mathbb{Z}^2$). One could hope to make some statement about maximum elements in this representation relating to maximum length cycles, but this is different than the congruences mentioned.

One could maybe hope to prove some statement about maximal elements in the above representation $(r_p, r_q)$, and then transfer (via exponentiation) to the "standard representation" and hope that they are "close to maximal". I would strongly expect this to be false though --- this property would be akin to being something like Lipschitz normally, which is much more regularity than I'd expect from these functions.

  1. Can we write other groups such as $(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)$, where $p, q$ are odd distinct primes, in terms of a free group as above? I am very glad if some guidance/steps to do so can be explained.

For $G\rtimes_\varphi H$ I explicitly include the homomorphism $\varphi : H \to \mathsf{Aut}(G)$ that the semi-direct product is defined with respect to.

The concept you're looking for is that of a group presentation. This is a way of writing a group $G$ as a set of generators $R$ and relations $S$ the generators satisfy (denoted $\langle R | S\rangle$). Equivalently, this is a way of writing a group $G$ as a free group on the generators $R$, quotiented by the normal subgroup generated by the relations $S$.

In this terminology, your question becomes "What is a group presentation of $(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)$?" It will be useful to know how group presentations behave under direct products and semi-direct products.

Let $G_1 = \langle R_1 | S_1\rangle$ and $G_2 = \langle R_2 | S_2\rangle$. Then:

  1. $G_1 \times G_2 = \langle R_1, R_2 | S_1, S_2, [R_1, R_2]\rangle$

  2. $G_1\rtimes_\varphi G_2 =\langle R_1, R_2 | S_1 , S_2, \forall (r_1, r_2)\in R_1\times R_2 : r_2 r_1^{-1}r_2 = \varphi(r_2)(r_1)\rangle$

Here $[A, B]$ is the commutator subgroup.

One should be able to use the above "transformation rules" (along with the presentation $\mathbb{Z}_p = \langle g | g^p = e\rangle$ for prime $p$) to compute a group presentation for the group you're interested in (or any other group built from direct and semi-direct products of cyclic groups).

$\endgroup$
7
  • $\begingroup$ Thank you very very much @Mark I am very grateful for the explanation and all the links of references added. If possible please add a link or give a hint on, where I can find more info on visualizing the paths on Cayley graph as paths in the lattice $\mathbb{Z}^2$. It is very interesting. $\endgroup$
    – Bob Traver
    Jun 4, 2020 at 17:15
  • $\begingroup$ Many many thanks again! $\endgroup$
    – Bob Traver
    Jun 4, 2020 at 17:15
  • 1
    $\begingroup$ @BobTraver You can view $(\mathbb{Z}/pq\mathbb{Z})^*\cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^*$ in two ways (corresponding to the "left" side of the isomorphism, or the "right" side). In the "right" side, there is a clear interpretation to visualize paths on the cayley graph as paths within $\mathbb{Z}^2$. The cayley graph can be viewed as the free (abelian) group on two generators $g_1, g_2$, quotiented by the relations $p\cdot g_1 = 0$ and $q\cdot g_2 = 0$. The free (abelian) group on two generators is simply $\mathbb{Z}^2$. Quotienting by these two relations gives us $\endgroup$
    – Mark
    Jun 4, 2020 at 22:30
  • 1
    $\begingroup$ $\mathbb{Z}^2$ but with points $(x,y)$ and $(a,b)$ identified if $a\equiv x\bmod p$ and $y\equiv b\bmod q$. We can therefore view this cayley graph as a rectangle within $\mathbb{Z}^2$ where the left and right sides are "connected" and the top and bottom are "connected". This object is often called a "torus". If you're familiar with lattices one can relate this graph to the fundamental domain of a fairly simple lattice (which is another way of viewing tori generically). $\endgroup$
    – Mark
    Jun 4, 2020 at 22:33
  • 1
    $\begingroup$ Also the aforementioend rectangle can be explicitly written as $[0, p)\times [0,q)$. Then the cayley graph is the graph on all lattice points within this rectangle, with the "wrapping around" rules that I mentioned before. This visualization requires knowing the factorization $N = pq$ though. $\endgroup$
    – Mark
    Jun 4, 2020 at 22:35

Your Answer

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

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