《现代密码学理论与实践》课程教学资源（参考资料）Random number MAX Period

已知Xn+1=aXn(mod2k),求{X}最大周期与对应的a值。 说明：对问题中k仅考虑k≥3的情形；当k=0,1,2时，可通过枚举，略。 解： 引理1：欧拉定理； 引理2：模m有原根的必要条件时m=1,2,4,p或2p,其中p是奇素数，∝≥1； (1)设对于某一a值，{Xn}最大周期为T(a),则 XT(a)+1=aT(a)X1 =X1(mod 2k) 即 aT(a)≡1(mod2k) 由引理1：欧拉定理可知φ(2k)=2k-1,则 T(a)2k-1 由引理2知，模2没有原根，则 T(a)≠p(2k),即T(a)≠2k-1 所以 T(a)l2k-2且T(a)≤2k-2 (2)考虑a的取值时，显然a应为奇数，可以分为a=8t士1与a=8t士3两种 情形。 a)当a=8t±3(t∈N)时，可由数学归纳法证明如下结论 T(a)2k-3, 1. 当k=3时， a2k-3=(8t±3)2*-3=(8t±3)2≠1(mod23) Ⅱ.假设k=r时，存在 a2r-3≠1(mod2) 当k=r+1时， a2-2-1=(a2r-3-1)(a2-3+1)

已知𝐗𝐧+𝟏 = 𝐚𝐗𝐧(𝐦𝐨𝐝 𝟐 𝐤 )，求{ Xn }最大周期与对应的 a 值。 说明:对问题中 k 仅考虑 k≥3 的情形；当 k=0,1,2 时，可通过枚举，略。 解： 引理 1：欧拉定理； 引理 2：模 m 有原根的必要条件时 m = 1,2,4,p ∝或2p ∝,其中 p 是奇素数，∝≥ 1； (1) 设对于某一 a 值，{ Xn }最大周期为 T(a)，则 XT a +1 ≡ a T(a)X1 ≡ X1(mod 2 k ) 即 a T(a) ≡ 1(mod 2 k ) 由引理 1：欧拉定理可知φ 2 k = 2 k−1，则 T a |2 k−1 由引理 2 知，模 2 k 没有原根，则 T(a) ≠ φ(2 k )，即T(a) ≠ 2 k−1 所以 T a |2 k−2且 T(a) ≤ 2 k−2 (2) 考虑 a 的取值时，显然 a 应为奇数，可以分为 a=8t±1 与 a=8t±3 两种 情形。 a) 当a = 8t ± 3 (t ∈ N)时，可由数学归纳法证明如下结论 T a ∤ 2 k−3， I． 当k = 3时， a 2 k−3 = (8t ± 3) 2 k−3 = (8t ± 3) 2 0 ≠ 1(mod 2 3 ) II． 假设k = r时，存在 a 2 r−3 ≠ 1(mod 2 r ) 当k = r + 1时， a 2 r−2 − 1 = a 2 r−3 − 1 (a 2 r−3 + 1)

由于a2r-3+1(mod2) 所以a2-3-1=2b.Q1,其中b2k-3 再结合(l)中结论可知，在a=8t±3(t∈N时，T(a)=2k-2。 b)当a=8t±1(t∈N)时，由相同方法可知.T(a)≤2k-3。 综上所述，当a=8t±3(t∈N)时，有最大周期2k-2

由于a 2 r−3 ≠ 1(mod 2 r ) 所以a 2 r−3 − 1 = 2 b ∙ Q1，其中b 2 k−3 再结合(1)中结论可知，在a = 8t ± 3 (t ∈ N)时，T a = 2 k−2。 b) 当a = 8t ± 1 (t ∈ N)时，由相同方法可知. T(a) ≤ 2 k−3。 综上所述，当a = 8t ± 3 (t ∈ N)时，有最大周期2 k−2