形如x<,i+2>≡ax<,i+1>+bx<,i>+c(mod M)的截尾同余序列的综合

• 作 者: 王丽萍 周锦君 韩付成
• 机 构: 信息工程学院应用数学系
• 出 处: 中国数学会第四届中国密码学学术会议
• 发表日期: 1996年期
• 关键词: 多项式时间 同余 高效算法 输出比例 参数恢复 输出值

该文就形如ｘ＜，ｉ＋２＞≡ａｘ＜ｉ＋１）＋ｂｘ＜ｉ＞＋ｃ（ｍｏｄ Ｍ）的截尾同余序列的序列恢复和参数恢复问题进行讨论。主要结果是给出两个高效算法。首先当ａ，ｂ，ｃ，Ｍ已知，给定截尾同余序列的前几个输出值，ａ为输出比例，ａ＞２／３或ｂ给定一定的范围，只要ａ＞５／８时给出多项式时间内恢复整个序列的算法。其次当参数ｂ已知，ｃ＝０，ａ要求同上，在给定一段连续长约为Ｏ（（ｌｏｇＭ）＜’１／２＞）的截尾同余序列时，给出多项式时间内恢复ａ，Ｍ的算法。