RSA assumption and relationship given by generating elemts of a Cayley graph

Question

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?

2. 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.

Answer 1

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.

2. 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).