如何證明 f(x)=m^x mod N 的周期性？

12-29

附加條件：m，N，x ∈N* 且 m& 驗算一下該函數確實有周期性，比如f(x)=2^x mod 3，周期T=2。

以上圖片出自一篇密碼學文章：http://www.freebuf.com/news/75346.html

數列 $f(x)$ 具有馬爾可夫性， $f(x+1)$ 由 $f(x)$ 完全確定。由此可以把 $f(x)$ 的所有取值看成點，從 $f(x)$ 到 $f(x+1)$ 連一條邊，形成一個圖。圖中的點數是有限的，而每個點都有後繼，所以必然形成環。

抽屜原理（也叫鴿巢原理），f(x)只有N個可能的取值，那麼f(0)到f(N)一共N+1個值中一定有兩個值是相等的，而一旦存在f(u) = f(v) （u≠v）就意味著接下來都是循環的。

更詳細一點，如果f(u) = 0，則接下來肯定都是0，這種情況出現的條件是n的所有質因子都是m的質因子。當n和m互質的時候，這種情況是不可能出現的，而且有m^φ(n) = 1 (mod n)，因此周期一定是φ(n)的一個約數。φ(n)是歐拉函數，代表1到n-1中，與n互質的整數的個數。

非互質的情況，可以通過從n中除掉所有m的質因子，轉化成互質的情況來討論。

另外，當m和n互質的時候，f(x)是個純周期函數，也就是說從f(0)開始就是周期的一部分（因為f(0) = 1, f(φ(n)) = 1）。當m和n不互質的時候，有可能開頭的幾個數不是周期的，後面才開始周期重複。

謝 @barries cran 邀。

首先本函數未必有周期性。
比如考慮2^x(mod 8)，取值依次是2,4,0,0,0,...，不滿足周期性的定義。
但如果說最終會陷入一個周期循環的局面(比如上面的000循環)，那是一定的。因為本函數的取值是有限的，所以一定會存在最小的x和y(x&根據euler定理，如果m和n互質，則必然是周期函數，T為φ(n)。
但如果m和n不互質，那也有可能是周期函數，比如4^x(mod 6),是取值恆為4的常數函數。

已經有直觀的答案了，我來寫一個容易看懂的形式化一點的證明吧。

因為f(x)這個函數的計算過程的最後一步是取N的模的運算，所以它的值域為小於N的自然數，最多可能有N個不同的值。

假設f(1)，f(2)，...，f(N+1)這個長度為N+1的數列中不存在兩個相等的數，則f(x)至少有N+1個不同的值。這與上面的結論矛盾，所以上述數列中必然存在兩個數f(A) = f(B)且A &< B。

令M = A - B，則有f(A) = f(A+M)。我們暫且把M稱為周期。

對任意正整數x，y有

f(x+y)

= m ^ (x+y) (mod N)

= m ^ x * m ^ y (mod N)

= (m ^ x (mod N)) * (m ^ y (mod N)) (mod N)

= f(x) * f(y) (mod N)

所以，對於[A+M, A+2M)範圍內的任何正整數x = A + M + w，有0 &<= w &< M且

f(A + M + w)

= f(A + M) * f(w) (mod N)

= f(A) * f(w) (mod N)

= f(A + w)

即第二個周期[A+M, A+2M)內函數的值是第一個周期[A, A+M)的重複。

對於之後任意一個給定的周期，通過有限次應用上述方法，都可以證明該周期內f(x)的值是第一個周期的簡單重複。