通过生成Cayley图给出RSA假设和关系

Question

我读到了与RSA组相关的非常有趣的计算描述如下。

“根据中国剩余定理，我们可以这样写：(\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})：(\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，其中e是群的恒等元，[g_q, g_p]是交换子等等。本质上，这是两个生成元上的自由交换群，受由CRT表示的生成元的阶的关系。

然后，我们可以用发电机g_q, g_p写出你所谈论的所有数量。说z = g_q^{z_q}g_p^{z_p}和y = g_q^{y_q}g_p^{y_p}。然后你的方程式：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给了我们“循环”。特别是，如果您将Cayley图看作是形式g_q^{x}g_p^{y}的顶点(因此我们可以将其形象化为\mathbb{Z}^2的某个子集)，这就减少了寻找循环的问题，比如(ry_q \equiv z_q \bmod (q-1))和(ry_p\equiv z_p\bmod (p-1))。您可能希望强制执行一些非琐碎的条件(如ry_q\neq z_q和ry_p\neq z_p)，我不确定。如果您想要找到最小/最大长度周期，那么您可以找到最小/最大的非平凡(y_q, y_p)，例如ry_q \equiv z_q\bmod (q-1)和ry_p\equiv z_p\bmod(p-1)。请注意，如果您知道N = pq的因式分解，您可以轻松地计算y_q \equiv r^{-1}z_q\bmod(q-1)和y_p\equiv r^{-1}z_p\bmod(p-1) (假设r在两个环中是可逆的)，然后通过搜索陪集r^{-1}z_q + (q-1)\mathbb{Z}找到具有所需属性的特定代表(y_p, y_q)。

(资料来源：凯莱图中圈给出的生成元素之间的关系)

我引用它只是因为我对它很感兴趣，请不要误解。

我想就此提出几个问题。

1. 为了求最大长度圈，它被看作是两个同余关系的最大解。但既然这些关系是一致的，我们怎么能证明最大值会给出与最长周期有关的答案呢？

例如，如果我们考虑a \equiv 0 (modp)，其中p是素数，而解决方案只能取\{0,1,2,...,p\}值，那么a只能取0或p的值。那么ry_q将永远是z_q？

( a)我尝试了上面的想法(只是为了方便地检查真值)，用于组\mathbb{Z}_3 \times \mathbb{Z}_5的Cayley图(无向)，其中生成元素是g_1=(0,1)和g_2=(1,0)，|g_1|=5, |g_2|=3。那么对于哈密顿循环g_1^{m} g_2^{n}=e，我能写m \equiv 0 (mod5)和n \equiv 0 (mod3)吗？

( b)这个图中有几个Hamiltonian圈，所以当我手动测试它的一个循环是m=0, n=3，而另一个循环是m=5,n=0。那么，如果我们把解作为上述方程的最大解来求解，我就得到了m=0,5和n=0,3组合的几个解对。我说的对吗？

1. 我们是否可以编写其他组，如(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes (\mathbb{Z}_q \times \mathbb{Z}_q)，其中p,q是奇数不同的素数，就像上面这样的自由组？我很高兴能解释一下这样做的一些指导/步骤。

Answer 1

1. 为了求最大长度圈，它被看作是两个同余关系的最大解。但既然这些关系是一致的，我们怎么能证明最大值会给出与最长周期有关的答案呢？

看起来不应该，我很确定我在把Cayley图中的循环形象化为格\mathbb{Z}^2中的路径。这与RSA组中的视图点对应为元组(g_p^{r_p}, g_q^{r_q}) (其中(r_p, r_q)\in\mathbb{Z}^2)。人们可以希望在这个表示中对最大元素作一些关于最大长度圈的说明，但这与所提到的同余不同。

人们可能希望证明上述表示(r_p, r_q)中关于极大元素的一些陈述，然后(通过指数法)将它们转化为“标准表示”，并希望它们“接近极大”。我强烈地认为这是错误的--这个性质类似于通常的Lipschitz，这比我从这些函数中所期望的更有规律。

1. 我们是否可以编写其他组，如(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)，其中p, q是奇数不同的素数，就像上面这样的自由组？我很高兴能解释一下这样做的一些指导/步骤。

对于G\rtimes_\varphi H，我显式地包含了半直积定义的同态\varphi : H \to \mathsf{Aut}(G)。

您要寻找的概念是小组演示。这是一种将组G编写为生成器R和生成器满足的关系S (表示为\langle R | S\rangle)的方法。等价地，这是一种将群G写成生成元R上的自由群的方法，由关系S生成的正规子群商。

在这个术语中，您的问题变成“什么是(\mathbb{Z}_p\times\mathbb{Z}_p)\rtimes_\varphi(\mathbb{Z}_q\times\mathbb{Z}_q)的组演示文稿？”了解小组演示文稿在直接产品和半直积下的行为将是非常有用的。

让G_1 = \langle R_1 | S_1\rangle和G_2 = \langle R_2 | S_2\rangle。然后：

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

这里[A, B]是换向器子群。

您应该能够使用上面的“转换规则”(以及表示\mathbb{Z}_p = \langle g | g^p = e\rangle表示素数p)来计算您感兴趣的组(或由循环组的直接和半直接乘积构建的任何其他组)的组表示。