2階排列組合的奇怪現象
假設 $ f,g,h:X\rightarrow X $ 是這樣的排列 $ f^{2}=g^{2}=\textrm{Id}{X} $ （IE $ f,g $ 有訂單2）。讓 $ F=f\circ g $ . 讓 $ D{f,g} $ 是取值的分佈 $ n $ 在哪裡 $ n $ 是最小的正整數，使得 $ F^{n}(x_{0})=x_{0} $ 對於隨機選擇 $ x_{0} $ .
因此，如果 $ f,g $ 隨機選擇，然後是期望值 $ E(D_{f,g}) $ 周圍有訂單 $ |X| $ 機率很高。但是，根據我的經驗，如果 $ f,g $ 不是隨機選擇的，它們彼此之間有某種關係，那麼 $ E(D_{f,g}) $ 經常非常接近任何一個 $ \sqrt{|X|},2\sqrt{|X|},4\sqrt{|X|},\frac{4}{3}\sqrt{|X|} $ . 此外，如果 $ f_{1},g_{1},f_{2},g_{2} $ 都以某種神秘的方式密切相關，那麼
$$ \frac{E(D_{f_{1},g_{1}})}{E(D_{f_{2},g_{2}})} $$通常非常接近 $ 1 $ . 例如，假設 $ X={0,1}^{n}\times{0,1}^{n} $ 和 $ R,S:{0,1}^{n}\rightarrow{0,1}^{n} $ 是隨機選擇的函式。讓 $ f(x,y)=(x,y\oplus R(x)),g(x,y)=(x\oplus S(y),y) $ . 然後 $ f,g $ 是相關的 2 階排列，其中 $ E(D_{f,g}) $ 通常在 $ 2^{n} $ （即使當 $ f $ 和 $ g $ 更複雜。很難說這種現象何時會持續）。
- 這種現象的數學解釋是什麼？
- 有什麼方法可以預測 $ E(D_{f,g}) $ 什麼時候 $ f,g $ 有一個簡單的描述並且易於計算嗎？
- 我想知道這種現像是否會導致由二階排列構成的對稱密碼系統中的不安全性。例如，假設 $ f,g $ 是二階密切相關的排列，並假設 $ h $ 是 2 階的另一種排列。讓 $ \ell_{0}=f\circ g $ 和 $ \ell_{1}=f\circ g\circ h $ . 假設對於擴展鍵 $ a_{0}\dots a_{n-1} $ ，塊加密函式為
$$ E_{a_{0}\dots a_{n-1}}=\ell_{a_{n-1}}\circ…\circ \ell_{a_{0}}. $$ 那麼塊加密功能是否存在任何加密弱點 $ E $ ? 特別是，是否存在由加密函式的 Matyas-Meyer-Oseas 構造引起的加密散列函式引起的任何安全漏洞 $ E $ ? 我應該懷疑這種形式的密碼系統可能存在的弱點嗎？
所以事實證明，2階隨機排列的組成並沒有什麼奇怪的。問題是一個元素在操作下的軌道大小的分佈 $ g\circ f $ 在哪裡 $ f,g $ 是否對合很大程度上取決於函式的固定點數 $ f,g $ 而如果 $ f $ 或者 $ g $ 有大量的不動點，那麼 $ g\circ f $ 有小軌道。
計算迭代時 $ (f\circ g)^{k}(x) $ , 當遇到函式的不動點時 $ f $ 或函式的 $ g $ 在返回之前 $ x $ ，開始計算迭代 $ (f\circ g)^{k}(x) $ . 在取消計算後迭代 $ (f\circ g)^{k}(x) $ ，一個最終取消計算回到 $ x $ ，此時，開始計算 $ (f\circ g)^{-k}(x) $ . 計算時 $ (f\circ g)^{-k}(x) $ , 最終遇到函式的另一個不動點 $ f $ 或函式的 $ g $ . 此時，反轉計算方向，直到返回 $ x $ 在一個完整的軌道上。找到第一個不動點所花費的時間服從指數分佈，並且在交叉後找到第二個不動點所花費的時間 $ x $ 也遵循具有相同參數的指數分佈。因此，完成一個完整的軌道所需的時間將是 $ X+X $ 對於一些指數分佈 $ X $ . 的機率密度函式 $ X+X $ 是 $ xe^{-x} $ 然而，直到重整化。
觀察到每個排列都可以寫成兩個對合的組合。然而，與其他排列相比，某些排列作為兩個對合的組合出現的機率要高得多。
認為 $ 1\leq r\leq k $ . 如果 $ h:[k]\rightarrow[k] $ 是一個隨機排列，那麼軌道的大小相對於 $ h $ 隨機元素的 $ x $ 是 $ r $ 正是 $ \frac{1}{k} $ . 假設 $ f,g:[2k]\rightarrow[2k] $ 是隨機選擇的排列，其條件是 $ f,g $ 沒有固定點。然後讓 $ P_{k,r} $ 表示軌道相對於 $ g\circ f $ 隨機元素的 $ x\in[2k] $ 有基數 $ 2r $ . 然後，在執行精確計算之後 $ P_{k,r} $ , 通過取極限, 得到 $ \lim_{n\rightarrow\infty}n\cdot P_{n,\lfloor nx\rfloor}=\frac{1}{2\sqrt{1-x}} $ 對所有人 $ x\in(0,1) $ （換句話說， $ x $ 可能有一個非常大的軌道）。
現在假設 $ f,g:[k]\rightarrow[k] $ 是隨機選擇的排列，其條件是 $ {x\in[k]|f(x)\neq x}=2m,{x\in[k]|g(x)\neq x}=2n $ . 然後讓 $ P_{m,n,k,r} $ 表示隨機元素的軌道有長度的機率 $ r $ .
那麼對於 $ x>0 $ ， 我們有 $ \frac{k\cdot P_{n,n,k,v}}{k-2n}\rightarrow xe^{-x} $ 作為 $ v\cdot\frac{k-2n}{k}\rightarrow x,k\rightarrow\infty,v\rightarrow\infty $ . （我可能會在稍後詳細說明為什麼會出現這種情況）。
現在，請注意具有機率密度函式的分佈的期望值 $ x\cdot e^{-x} $ 是 $ 2 $ . 因此，隨機元素軌道大小的期望值接近 $ \frac{2k}{k-2n} $ . 在問題中概述的場景中，功能 $ f,g $ 通常有 $ O(\sqrt{|X|}) $ 許多固定點可以確保周圍有 $ \frac{2k}{k-2n} $ 許多固定點。