混合线性同余发生器(MLCG)
X
n ≡ αX
n-1 + c mod m 0<X
0, α, c<m,X
0为种子,n=1、2、3...
定理 如果下列3个条件都满足,则 MLCG达到满周期(即周期d=m)
(1) (c, m)=1,即 c、m互素
(2) 对 m的任一素因子p,有α≡1 mod p
(3) 如果4|m,则 α≡1 mod 4
该定理的证明在
参考文献[2]中证明并用到如下引理:
引理5 设p为素数,α∈Z+且pα>2,如果 x=1(mod pα),x≠1(mod pα+1);则xp=1(mod pα+1), xp≠1(mod pα+2)
本文主要阐述为什么p是使x
p=1(mod p
α+1)成立的最小正整数,以及一般情形m=p
w(w≥1)是使x
m=1(mod p
α+w)成立的最小正整数
◆ 先论证不存在一个整数1≤b<p使得x
b=1(mod p
α+1)成立
◆ 再证不存在一个整数1≤b<m使得x
b=1 (mod p
α+w)成立
参考文献
[1] 现代密码学第4版 杨波
[2] 混合线性同余发生器的周期分析 张广强、张小彩