随笔-155  评论-223  文章-30  trackbacks-0
混合线性同余发生器(MLCG)      
      Xn ≡ αXn-1 + c mod m    0<X0, α, c<m,X0为种子,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)
    该引理给出了求一个整数的阶的判别方法,是理解MLCG周期等于m的充要条件之关键。
    本文阐述为什么p是使xp=1(mod pα+1)成立的最小正整数,以及一般情形m=pw(w≥1)是使xm=1(mod pα+w)成立的最小正整数;为什么前提条件是pα>2。

    ◆ 先论证不存在一个整数1≤b<p使得xb=1(mod pα+1)成立
       
    ◆ 再证不存在一个整数1≤b<m使得xb=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是奇数,则x2=1(mod22),x2=1(mod23)。故得不到引理的结论

  引理6(改写的等价形式) 如果 α=1(mod 4),则(αm - 1)/(α - 1)=0(mod m) ,m=2w,w>1
     其实这里当α=1(mod 2)且α≠1(mod 4),结论也是成立的。比如取α=3,m=16,则 (316 -1)=814 -1=(-15)4 -1=-15×-7×-7 -1=-15×-15 -1=9×-7 -1=0(mod 32),
     即(316 -1)/(3-1)=0(mod 16)。但只有当α=1(mod 4)时,m才是使结论成立的最小正整数。论证如下
         

参考文献    
     [1] 现代密码学第4版 杨波    
     [2] 混合线性同余发生器的周期分析 张广强、张小彩
posted on 2024-03-12 17:30 春秋十二月 阅读(594) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理