給定一個循環x↦X一個X↦X一個x mapsto x^a以他的出發點X1X1x_1.能否換個起點X2X2x_2被改造以產生相同的循環？
可以產生一個循環序列
$$ s_{i+1} = s_i^a \mod N $$ 和 $ N = P \cdot Q $ 和 $ P = 2\cdot p+1 $ 和 $ Q = 2\cdot q+1 $ 和 $ P,Q,p,q $ 素數。
和 $ a $ 的一個原始根 $ p $ 和 $ q $ .
起點 $ s_0 $ 是一個正方形 ( $ \mod N $ )
會產生一個循環長度 $ \mathrm{lcm}(p-1.q-1) $
（除了 $ s_0 $ 是一個 $ p $ -雷神 $ q $ -次冪 $ \mod N $ )
現在給出一個起點 $ s_0 = x_1 $ 它會產生這樣一個循環序列。
給定另一個起點 $ s_0 = x_2 $ 它將生成一個相同長度的循環序列，但它具有完全不同的成員。
有什麼辦法可以改造 $ x_2 $ 所以它會產生相同的循環序列 $ x_1 $ 做？
（編輯：發布的答案是如果有的話，而不是如何，與問題相同，將其標記為答案）
（與this的答案有關）
更新：
看起來不同周期的數量 $ N_c $ 是： $$ N_c = (S_N - S_{pq}) /L_c $$ $$ S_N = |{ v^2 \mod N}| \text{ with } v\in[1,N-1] $$ $$ L_c = \mathrm{lcm}(p-1.q-1) $$ 和 $ S_{pq} $ 正方形的數量也是 $ p $ -th, $ q $ -次冪 $ \mod N $ .
$ S_N $ 可能總是大於 $ \frac{1}{4}N $
在一些測試中 $ N=3901 $ 和 $ P=47 $ , $ Q=83 $ , $ a = 7 $ （或者 $ 11, 17, 19,.. $ ) 兩個週期是可能的 $ L_c =440 $ , $ S_N = 1006 $ , $ S_{pq}=127 $ .
一 $ x1 $ 可以轉換為來自另一個循環的值（以 $ x_2 $ ) 有一個指數 $ b $ 喜歡 $ x_1^b \mapsto s_i\in \mathrm{cycle}_{x_2} $
這個指數需要 $ b \in [3 , 5 , 6 , 10 , 12 , 13, 20 , 21 , 24 , 26 , 27 , 29 , 33 , 35 , 37, 40, 42 , 43 , 45, 47, …] $
不知道為什麼這些值確實有效。
為了 $ N=40633, P= 179, Q= 227 $ 和 $ S_N= 10259 $ 正方形，包括 $ S_{pq}= 403 $ 它有 $ 8 $ 有長度的循環 $ L_c= 1232 $ . 指數 $ a $ 用於序列生成可以是 $ a\in[3, 19, 23, 29, 43,..] $
對於這個指數 $ b $ 需要 $ b \in [7 , 13, 17 , 21, 28 , 39 , 51 , 52 , 62 , 63 , 68 , 71 , 79 , 84 , 110 , 112 , 117,125,..] $
應用這些指數中的任何一個 $ b $ 到一個起始值 $ x_0 $ 將導致下一個序列的循環。這個循環序列順序對於每個指數都是相等的 $ b $ .
在分析這樣的案例時，查看行為模數很有用 $ P $ 和模 $ Q $ 分開，然後看看它們是如何結合的。我將添加以下假設 $ P \ne Q $ ; 您沒有明確表示；我相信你假設它是合理的。
當我們看循環結構模 $ P $ ，我們首先看到 $ s_0 \bmod P $ 是二次餘數模 $ P $ （這是說“它是一個正方形”的數學方式）；自從 $ a $ 是原根 $ p $ ，那麼我們看到有三個循環：
- 長度為 1 的循環（值 0）
- 另一個長度為 1 的循環（值 1）
- 一個循環的長度 $ p-1 $ ; 這是因為 $ a^i \bmod p-1 $ 是范圍內的不同值 $ [0, p-2] $ ， 和 $ s_0 $ 有訂單 $ p-1 $ （在這個組中，除 1 之外的二次殘差總是那個順序），所以 $ s_0^{a^i} $ 是 $ p-1 $ 不同的價值觀。
我們在觀察行為模數時得到了類似的結果 $ Q $ .
鑑於這些基礎知識，它們如何結合？
嗯，循環模 $ PQ $ 僅當兩個循環模數時才重複 $ P $ 重複和循環模 $ Q $ 重複；如果 $ P $ -cycle是長度 $ \alpha $ 和 $ Q $ -cycle是長度 $ \beta $ , 這個聯合循環有長度 $ \text{lcm}(\alpha, \beta) $ .
這意味著兩個大周期的任何組合都有長度 $ \text{lcm}(p-1,q-1) $ （這是您已經找到的結果）。而且，有 $ \gcd(p-1,q-1) $ 這兩個大周期可以結合的方式。
我們現在考慮一個包含小循環的組合；我們有兩種循環長度組合 $ p-1 $ , 有循環長度的兩種組合 $ q-1 $ ，以及循環長度為 1 的四種組合（包括 $ s_0 = 0 $ 和 $ s_0 = 1 $ ).
因此，總週期數為 $ \gcd(p-1, q-1) + 8 $ .
而且，回答你的問題：
有什麼辦法可以改造 $ x_2 $ 所以它會產生相同的循環序列 $ x_1 $ 做？
好吧，對於任何整數 $ \beta $ ， 我們有 $ s_{i+1}^\beta = (s_i^\beta)^a $ . 也就是說，如果我們取循環的每一個元素，並將其提升到冪次 $ \beta $ ，我們還有一個循環。
所以，如果我們有價值 $ \beta $ 為此 $ x_2^\beta = x_1 $ ，那麼這為我們提供了一種將一個循環轉換為另一個循環的方法。
原來總是有這樣的 $ \beta $ 如果兩個週期都很大（即，長度 $ \text{lcm}(p-1, q-1) $ ）。對於退化循環（所有其他循環），不會有 - 但是，我認為這種情況並不有趣……
當然，找到這樣一個 $ \beta $ 給定 $ x_1, x_2 $ 是一個不平凡的問題，如果 $ P, Q $ 很大…