IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

    混合线性同余发生器一个引理的验证

    春秋十二月发表于 2024-03-12 09:30:00
    love 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)
      本文主要阐述为什么p是使xp=1(mod pα+1)成立的最小正整数,以及一般情形m=pw(w≥1)是使xm=1(mod pα+w)成立的最小正整数

      ◆ 先论证不存在一个整数1≤b<p使得xb=1(mod pα+1)成立
           
      ◆ 再证不存在一个整数1≤b<m使得xb=1 (mod pα+w)成立
           

    参考文献
        [1] 现代密码学第4版 杨波
        [2] 混合线性同余发生器的周期分析 张广强、张小彩


    春秋十二月 2024-03-12 17:30 发表评论


沪ICP备19023445号-2号
友情链接