混合線性同余發(fā)生器（MLCG）
X
n ≡ αX
n-1 + c mod m 0<X
0, α, c<m，X
0為種子，n=1、2、3...
定理 如果下列3個(gè)條件都滿足，則 MLCG達(dá)到滿周期(即周期d=m)
(1) (c, m)=1，即 c、m互素
(2) 對(duì) m的任一素因子p，有α≡1 mod p
(3) 如果4|m，則 α≡1 mod 4
該定理的證明在
參考文獻(xiàn)[2]中證明并用到如下兩個(gè)引理：
引理5 設(shè)p為素?cái)?shù)，α∈Z+且pα>2，如果 x=1(mod pα)，x≠1(mod pα+1)；則xp=1(mod pα+1)， xp≠1(mod pα+2)
該引理給出了求一個(gè)整數(shù)的階的判別方法，是理解MLCG周期等于m的充要條件之關(guān)鍵。
本文闡述為什么p是使x
p=1(mod p
α+1)成立的最小正整數(shù)，以及一般情形m=p
w(w≥1)是使x
m=1(mod p
α+w)成立的最小正整數(shù)；為什么前提條件是p
α>2。
◆ 先論證不存在一個(gè)整數(shù)1≤b<p使得x
b=1(mod p
α+1)成立
◆ 再證不存在一個(gè)整數(shù)1≤b<m使得x
b=1 (mod p
α+w)成立
◆ 為什么前提條件是pα>2
如果pα=2，x=1(mod 2)且x≠1(mod 22)。令x=1+2q，2 ∤ q。有x2=(1+2q)2=1+4q+4q2，注意到q是奇數(shù)，則x2=1(mod22)，x2=1(mod23)。故得不到引理的結(jié)論
引理6（改寫的等價(jià)形式） 如果 α=1(mod 4)，則(αm - 1)/(α - 1)=0(mod m) ，m=2w，w>1
其實(shí)這里當(dāng)
α=1(mod 2)且
α≠1(mod 4)，結(jié)論也是成立的。比如取
α=3，m=16，則 (3
16 -1)=81
4 -1=(-15)
4 -1=-15×-7×-7 -1=-15×-15 -1=9×-7 -1=0(mod 32)，
即(3
16 -1)/(3-1)=0(mod 16)。但只有當(dāng)
α=1(mod 4)時(shí)，m才是使結(jié)論成立的最小正整數(shù)。論證如下
參考文獻(xiàn)
[1] 現(xiàn)代密碼學(xué)第4版 楊波
[2] 混合線性同余發(fā)生器的周期分析 張廣強(qiáng)、張小彩
posted on 2024-03-12 17:30
春秋十二月 閱讀(1459)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
Algorithm