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