密码编码学与网络安全第七版习题 8.2
这道题是密码学的作业，开始不会写，答案只有结果而没有过程，后来查了一些资料才算是搞明白了。
题目如下：
- 下述的伪随机数发生器可获得的最大周期是多少？
\[ X_{n+1}=(aX_n)\mod{2^4} \]
这时 a 为多少？
对种子有什么要求？
解答如下：
(a)
首先引入这样一个结论：对任意的奇数\(a\)与正整数\(n\)，有：\(a^{2^n}≡1\pmod{2^{n+2}}\)。用归纳法证明这个结论：
当\(n=1\)时，存在整数\(b\)，\(c\)，使得
\[ a^{2^n}=(2b+1)^2=4b(b+1)+1=2^3c+1≡1\pmod{2^3} \]
假设当\(n=k\)时，命题成立，即
\[ a^{2^k}≡1\pmod{2^{k+2}} \]
则存在整数\(c\)，使得
\[ a^{2^k}=2^{k+2}c+1 \]
当\(n=k+1\)时，存在整数\(k\)，\(b\)，使得
\[ a^{2^{k+1}}=(2^{k+2}c+1)^2=2^{2k+4}c^2+2·2^{k+2}c+1=2^{k+3}c(2^{k+1}c+1)+1≡1\pmod{2^{k+3}} \]
即当\(n=k+1\)时，命题成立。
由 1，2 可得，该命题成立。
若\(a\)与\(2^4\)不互素，即\(a\)为偶数，令\(a=2k\)，则
\[ a^4=16k^4≡0\pmod{2^4} \]
从而
\[ 0=X_{n+4}≡a^4X_n\pmod{2^4} \]
产生的第四个数之后全为 0，所以\(a\)与\(2^4\)互素。
又因为
\[ a^{2^n}≡1\pmod{2^{n+2}} \]
所以
\[ a^{2^{4-2}}=a^4≡1\pmod{2^4} \]
从而
\[ a^4X_n≡X_n\pmod{2^4} \]
即
\[ X_{n+4}=X_n \]
所以最大周期为 4。
(b)
由(a)可知，\(a\)为奇数。
经计算，\(a=7,9,15\)时，周期为 2。
\(a=3,5,11,13\)时，周期为 4。
(c)
种子必须为奇数，否则周期会不大于 2。