計算乘法組中給定順序的元素n=pq_n=pqn=pq(RSA)
我們知道元素的順序 $ a $ 在群裡 $ \mathbb Z_n^* $ 是 $ k $ 在哪裡 $ k|lcm(p-1,q-1) $ 其中 p,q 是不同的素數。
我認為我們知道的另一件事是，有秩序的元素 $ lcm(p-1,q-1) $ 將準確生成 $ \frac{φ(n)}{lcm(p-1,q-1)} $ 可能具有共同元素的不同子組（以便共同生成組的所有元素）。基於此，如果 n 是素數，我們可以通過以下方式輕鬆計算每個訂單的元素 $ φ(order) $ . （如果它是素數，一個元素可以生成所有其他元素）
是否可以計算給定順序的元素數量？
例如： $ n=5*7 $
有多少個元素有 6 階？（我知道它是 6，但是有沒有通用的方法可以找到它？）
在這種情況下，CRT 可以給出一個近似值，但您仍然應該過濾掉在這種情況下除以 6 (1,2,3) 的階數較小的元素。
以下是順序為 12 的子組：
2,4,8,16,32,29,23,11,22,9,18,1 3,9,27,11,33,29,17,16,13,4,12,1 12,4,13,16,17,29,33,11,27,9,3,1 17,9,13,11,12,29,3,16,27,4,33,1 18,9,22,11,23,29,32,16,8,4,2,1 23,4,22,16,18,29,2,11,8,9,32,1 32,9,8,11,2,29,18,16,22,4,23,1 33,4,27,16,3,29,12,11,13,9,17,1一個有趣的細節是每個組的生成器恰好存在於其他三個子組。例如，33 在 3、12、17 個子組內。（每個都包含位置 m 中的其他元素，其中 $ gcd(m, 12)=1 $ 所以我們有兩個子組中的每一個的 4 個排列）
訂單 6：
4,16,29,11,9,1 9,11,29,16,4,1 19,11(-24),34,16,24,1 24,16(-19),34,11,19,1 26(-9),11,6,16,31,1 31(-4),16,6,11,26,1在這裡，每個生成器都存在於另一個子組中
編輯：
我的第二個定理似乎有點缺陷：我假設結合所有的子群 $ lcm(p-1,q-1) $ 將生成乘法群 n 的所有元素。但正如我們從我的範例中看到的那樣，它們不會，因為它們不會生成元素 6、19、24、26、31、34。
這裡有一些很好的資源，可能很有用。組 mod n和carmichael 函式。
不難計算，精確有序的元素個數 $ r $ 是：
$$ F_{p-1, q-1}( \phi(r)) $$
在哪裡 $ F $ 是這個功能：
如果素數分解 $ r = r_1^{e_1} r_2^{e_2} … r_n^{e_n} $ 然後
$$ F_{p-1, q-1}(r) = F_{p-1, q-1}(r_1^{e_1}) \cdot F_{p-1, q-1}(r_2^{e_2}) \cdot … \cdot F_{p-1, q-1}(r_n^{e_n}) $$
如果 $ s $ 是素數並且 $ e>0 $ ， 然後 $ F_{p-1, q-1}(s^e) $ 取決於 $ \gcd( s^e, p-1) = s^a $ 和 $ \gcd( s^e, q-1) = s^b $
如果 $ a, b < e $ ， 然後 $ F_{p-1, q-1}(s^e) = 0 $ （即沒有具有該順序的元素）
如果 $ a=e, b < e $ ， 然後 $ F_{p-1, q-1}(s^e) = s^b $
如果 $ b=e, a< e $ ， 然後 $ F_{p-1, q-1}(s^e) = s^a $
如果 $ a=b=e $ ， 然後 $ F_{p-1, q-1}(s^e) = s^e + s^{e-1} $
這使我們能夠計算所有情況下的元素數量。