一种基于线性同余算法的伪随机数产生器.pdfVIP

维普资讯 2005年 9月 纯粹数学与应用数学 Sep．2005 第 21卷第 3期 PureandAppliedMathematics V0I．21NO．3 一 种基于线性同余算法的伪随机数产生器 马华，张晓清，张鹏鸽 (西安电子科技大学理学院，西安 710071) 摘 要：线性 同余算法作为使用最为广泛的伪随机数产生算法 ，具有产生速度快、输 出序列周期长等特点，但安全性能不佳的弱点始终制约着该算法在密码学领域的应 用．本文在对线性同余算法详细分析的基础上 ，给出了一种不受乘数 a选择限制的伪 随机数产生器．该算法具有 良好的伪随机性和安全性． 关 键 词：线性同余算法；随机数 ；产生器 中圈分类号： TN918．2文献标识码 ：A 文章编号 ：1008—5513(2005)03—0206—04 线性同余算法u别是使用最为广泛的伪随机数产生器．该算法含有4个参数：模数m(m O)，乘数a(0≤a ，，1)，增量c(O≤c ，，1)，初值即种子(Seed)X。(0≤X。，，1)．使用迭代公 式： += (口·X +c)modm得到随机数序列{ )．如果m，口，f，。都是整数，则产生的随机 数序列{ }也都是整数，且 0≤X m．只要满足条件0≤X ，X m，则 由它产生的序列 必具有周期性．a，c和 m的取值是产生高质量随机数 的关键．对于一个随机数产生器来说 ，只 要其产生的随机数序列的周期充分长，它就能够具有在(0，1)上均匀分布及相互独立的性质． 为使随机数序列的周期尽可能大，，，z应尽可能大．普遍原则是选m接近等于计算机能表示的最 大整数，如接近或等于2． 对于一个随机数产生器而言，衡量其优劣的标准有两个．其一是该产生器所产生的伪随机 数序列是否具有 良好的伪随机性；其二是该产生器的安全性，即敌手是否能够通过截获一组该 产生器所产生的伪随机数序列来正确地预测下面的序列，甚至是再现完整的伪随机数序列．在 线性同余算法X ： (口·X +c)modm中，参数c对该算法所产生的随机数序列所具有的伪 随机性没有影响．因此，我们在算法的实现中仅考虑 +=(口· )modm的情况．线性同余算 法的强度在于如果将乘数和模数选择得好，则产生的序列和从 1，2，…，m一1中随机选取的序 列是不可区分的．但是除了初值 o的选取具有随机性外，算法本身并不具有随机性，因为 。 选定后，以后的数就确定性地产生了．这个性质可用于对该算法的密码分析，如果敌手知道我 方正在使用线性同余算法并知道算法的参数，则一旦获得序列中的一个数，就可得到以后的所 有数．由于线性同余算法的安全性能不佳，所以无法应用于需要较高安全性的密码领域 内．本 较■ 日期 ：2004—11—08． 基盒项且：圈謇自然井学基全礴异． 作者 ■介#马华(1963一)，女 ，科教授 ，研究方向：蝙码 维普资讯 第 3期 马 华等 一种基于线性 同余算法 的伪随机数产生器 207 文从线性 同余算法出发，在保持原算法速度快的优点的同时，以获得良好的安全性能为目的对 原算法加以修改，产生出了一种不受乘数a选择限制的伪随机数产生器． 1 随机数产生器 X计l一 (口·X)modm 的实现 F面采考 虑 随机效严 生器 X +1 (口。 )modm 的买现 ·算 买现 町 ，焉妥】孵厌 明王曼J日J 题是溢出，文[1]曾针对此问题给出了以下两个算法． ‘ 算法 1 将迭代关系写为：X = ，(X)= (口·X)modm． 设 一口g·+r，其中g=-詈【J，r—m。d口． ，cx，=c口x·d：口x·— ·l j：L~j~Xm0dq— ·l j 一 dg)一 ·-【 =(m--，．， 一 ·-【j ～dq)一，．+c 一l j，