Cayley圖中由循環給出的生成元素之間的關係
強 RSA 假設是以下問題很難解決。
“給定一個隨機選擇的 RSA 模數 $ n $ 和一個隨機 $ z \in \mathbb{Z}_n^* $ ， 尋找 $ r>1 $ 和 $ y \in \mathbb{Z}_n^* $ 這樣 $ y^r=z $ 。”
RSA 假設可以寫成“在計算上很難在 RSA 組中找到一個非平凡的關係 $ (\mathbb{Z}/pq\mathbb{Z})^* $ “。所以在考慮凱萊圖時，尋找生成元素之間的關係的問題可以看作是在凱萊圖中尋找循環，因為循環給出了生成元素之間的關係。
（例如，假設凱萊圖由元素生成 $ s $ 和 $ t $ . 當我們沿著 $ sttstt $ ，假設我們沿著一個長度為 6 的循環進行了追踪。那麼因為它是一個循環， $ st^2st^2=e $ ，它實際上代表了生成元素之間的關係 $ s $ 和 $ t $ .)
當我們考慮發現的情況時 $ y $ 這樣 $ y^r=z $ 如上所述，我們不知道哪個週期賦予了這種特殊關係，對嗎？
有沒有辦法將其與循環的長度聯繫起來，以便我們了解哪種類型的循環給出了上述關係？
另外，我想到的另一個問題是，當找到 $ y $ ，我們也許可以通過使用私鑰或與所考慮的密碼系統相關的一些數據來使用代數方法。但是如果我們希望嘗試給出一個解決方案 $ y $ 雖然在圖中找到一個循環的過程，這將是非常困難的，對吧？
我的意思是即使對於消息的發送者和接收者來說也會很困難，因為找到週期需要時間，即使使用算法完成也是如此，對吧？
提前非常感謝。
根據中國剩餘定理，我們有： $$ (\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 $ )，這減少了尋找循環到尋找點的問題 $ (y_q, y_p) $ 這樣 $ (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 $ 在兩個環中都是可逆的），然後找到特定的代表 $ (y_p, y_q) $ 通過搜尋陪集獲得所需的屬性 $ r^{-1}z_q + (q-1)\mathbb{Z} $ .
我相信我們可以很容易地讀出任何週期的長度。特別是，循環是從 $ (0,0) $ 在 $ \mathbb{Z}^2 $ 至 $ (k_q, k_p) $ 這樣 $ k_q\equiv ry_q-z_q\bmod (q-1) $ 和 $ k_p\equiv ry_pz_p\bmod(p-1) $ . 從最短路徑的長度 $ (0,0) $ 至 $ (k_q, k_p) $ 因此 $ |k_q| + |k_p| $ ，這是你的周期的長度。作為 $ k_q\equiv 0\bmod(q-1) $ （同樣對於 $ k_p $ )，我們看到任何循環的長度必須是形式 $ |a_p|(p-1) + |a_q|(q-1) $ 對於非零整數 $ a_p, a_q $ ，這對可實現的可能長度設置了一些限制（這與Frobenius 硬幣問題有關）。可能有上限 $ a_p $ 和 $ a_q $ 來自類型的組關係 $ g_q^{q-1} $ ，但這需要首先定義一個好的“平凡”循環概念。
至於這個的可計算性，如果你知道它的因式分解，就可以有效地計算 $ N = pq $ （上面的所有討論都是這樣做的），並且（可能）不能沒有這個。我不知道以這種方式重寫 RSA 是否有任何好處（我沒有立即看到），並且不保證上面的計算是正確的，但它們至少對我來說似乎是正確的。
需要擔心的一件事是邊緣的緊湊表示。以上所有都需要知道的因式分解 $ N $ . 如果我們刪除它，那麼我們可以抽像地將凱萊圖視為 $ \phi(N) $ 頂點，它作為 $ p,q\approx 2^{n/2} $ 將會 $ \phi(N)\approx 2^n $ . 頂點可以通過索引來傳達 $ [\phi(N)] $ ，並且由於該圖是4-正則的（我認為，每個頂點的邊是 $ {g_p, g_p^{-1}, g_q, g_q^{-1}}) $ 每個特定的邊緣都可以被有效地描述。但我不知道如何有效地傳輸整個圖表，因為有 $ O(2^n) $ 邊，這意味著將其視為抽像圖意味著您無法有效地傳達它。
當然，有一些有效的方法可以“壓縮”圖形（這必須在傳統的基於 RSA 的密碼系統中隱式完成），但不清楚該壓縮中有多少會推廣到其他組，這似乎是您的意圖。