模冪運算總是循環的嗎？

在 RSA 中使用時鐘算法，正如費馬小定理所說， $ a^p \bmod p = a $ . 取冪是循環的， $ a^x = a^{x \bmod p-1} \bmod p $ ，在每個循環中重複相同的數字序列。所有模冪運算是否以類似的方式存在一個循環，或者僅適用於諸如素數模數之類的某些情況？

是的，如果 $ \gcd(a,n)=1 $ . 否則，我們仍然會達到一個循環，但它可能不會回到它開始的地方。

對於所有整數 $ n>0 $ , $ a $ , $ x $

• 什麼時候 $ \gcd(a,n)=1 $ ， 它擁有 $ a^x\equiv a^{(x\bmod\lambda(n))}\pmod n $ . 序列 $ a_j $ 定義為 $ a_0=1 $ , $ a_{j+1}=a\cdot a_j\bmod n $ 循環回到 $ 1 $ ， 然後 $ a\bmod n $ .

$ \lambda $ 是Carmichael 函式，其中 $ 1\le\lambda(n)<n $ 對所有人 $ n>1 $ .

最小周期 $ a_j $ 取決於 $ a $ 和 $ n $ . 它的一些除數 $ \lambda(n) $ ，稱為順序 $ a $ 模組 $ n $ . 這是 $ 1 $ 什麼時候 $ a\equiv1\pmod n $ . 這是 $ 2 $ 為了 $ a=n-1 $ 和 $ n>1 $ .

• 什麼時候 $ \gcd(a,n)\ne1 $ ， 序列 $ a_j $ 最終是周期性的，有一個週期劃分 $ \lambda(n) $ ，但序列的頭部可能不是周期的一部分。例如 $ a=2 $ , $ n=12 $ , $ a_0=1 $ , $ a_1=2 $ , $ a_2=4 $ , $ a_3=8 $ , $ a_4=4 $ .

引用自：https://crypto.stackexchange.com/questions/70658