Permutation
從兩個置換矩陣的乘積提高到相同的冪，很容易找到冪嗎？
讓 $ A $ 和 $ B $ 是兩個公共置換矩陣。如果 $ r $ 是一個大數的秘密力量，我們可以很容易地找到 $ r $ 從 $ A^rB^r $ ?
這是一個簡單的問題；我將概述如何解決它。
關鍵是循環結構。讓我們看看一個週期如何 $ A $ 被處理。
這個循環是一組 $ k $ 元素 $ (a_1, a_2, …., a_k) $ ; 什麼時候 $ A^r $ 所做的就是利用這些元素中的每一個並推進它們 $ r \bmod k $ 排列中的位置。並且，請注意，無論 $ r $ 是， $ a_i $ 將映射到一些 $ a_j $ ， 對於一些 $ j $ .
現在， $ B $ 具有（可能）完全不同的循環結構；價值 $ a_1 $ 可能是某個循環的一部分 $ (b_1, b_2, …, b_x) $ （為了 $ a_1 = b_1 $ )，而值 $ a_2 $ 可能是某個不同循環的一部分 $ (c_1, c_2, …, c_y) $ （為了 $ (a_2 = c_1) $ ）。而且，再一次，無論價值如何 $ r $ 是，如果我們開始 $ B $ 在一個特定的周期中，我們永遠不會離開它。
現在，我們取循環的元素 $ a_1, a_2, …, a_k $ ，並查看：
- 什麼循環 $ B $ 他們是
- 什麼循環 $ B $ 是 $ A^r B^r (a_i) $ （對於各種 $ i $ 是的一部分
如果潛在價值 $ r \bmod k $ 創造價值 $ a_i $ 至 $ a_j $ ， 和 $ a_j $ 是一個的一部分 $ B $ -循環，而 $ A^r B^r (a_i) $ 是不同的一部分，那個值 $ r \bmod k $ 是不可能的。
上述邏輯應該消除大部分可能的值 $ r \bmod k $ （假設排列是隨機生成的）；可以進行第二次檢查（這取決於循環中元素的相對順序）-您應該能夠自己弄清楚細節。