第20卷第5期2022年5月
太赫兹科学与电子信息学报
Journal of Terahertz Science and Electronic Information Technology
Vol.20，No.5
May，2022可逆线性同余随机数发生器
卫丽华1，管致锦*2，朱鹏程1
(1.宿迁学院信息与计算科学系，江苏宿迁223800；2.南通大学信息科学技术学院，江苏南通226019)
摘要：随机数的恢复是仿真系统实现时间回溯能力的关键问题之一，仿真系统通常包含大量随机数，为了恢复之前任意时刻的系统状态，就必须对随机数的状态演化进行跟踪和记录，这
种跟踪和记录工作需要极大的时间和空间代价。为解决仿真系统中的随机数恢复问题，基于可逆
计算的思想，提出一种可逆线性同余随机数发生器，并分别通过反函数、通项公式、逆分布函数
实现该随机数发生器，使其既可正向生成任意分布的随机数列，又可反向恢复之前的随机数。实
验结果表明该可逆随机数发生器在总的时空性能上较目前通用的Checkpointing实现方式优越。
关键词：可逆计算；线性同余法；随机数；仿真系统
中图分类号：TP301.6文献标志码：A doi：10.11805/TKYDA2020126
Reversible linear congruential generator
WEI Lihua1，GUAN Zhijin*2，ZHU Pengcheng1
(1.Department of Information and Computational Sciences，Suqian University，Suqian Jiangsu223800，China；
2.College of Information Science and Technology，Nantong University，Nantong Jiangsu226019，China)
Abstract
Abstract：：The recovery of random numbers is one of the key issues for the simulation system to realize the time traceability.The simulation system usually contains a large number of random numbers.
In order to restore the system state at any time before,it is necessary to track and record the state
evolution of the random number.This kind of tracking and recording work requires a great time and
space cost.In order to solve the problem of random number recovery in the simulation system,based on
the idea of reversible computation,a reversible linear congruential random number generator is
proposed,and the random number generator is realized through the inverse function,general term
formula,and inverse distribution function,respectively.It can not only generate random numbers in the
forward direction,but also recover the previous random numbers in the reverse direction.The
experimental results show that the reversible random number generator is superior to the current general
checkpointing implementation in terms of overall space-time performance.
Keywords
Keywords：：reversible computation；linear congruence approach；random number；simulation system
大型仿真系统的每一场景都包含大量数据，其中包含很多随机数[1]。概率分布数列经常被计算机用来模拟物理系统模型，随机数发生器用于生成符合一定概率分布的数列。目前关于随机数发生器的主要研究有：1)在一定精确度范围内，增加随机数的长度；2)提高发生器的生成速度；3)生成复杂分布数列；4)降低多个数列间的相互影响。Jhessica Clawdia等[2]使用线性同余发生器(Linear Congruential Generator，LCG)算法生成随机数。该算法可以避免生成重复随机数，增加随机数的长度。Mina Mishra等[3]主要对Matlab随机数发生器(Random Number Generator，RNG)和线性同余发生器(LCG)随机数发生器算法进行了测试，测试结果表明LCG算法具有抗密码分析攻击的能力和良好的密钥敏感性。Massoud Sokouti等[4]提出了一种基于遗传算法思想的线性同余(LCG)方法，增加了生成随机数的随机性。D Apdilah等[5]分别将线性同余发生器(LCG)和二次同余发生器(Quadratic Congruential Generator，QCG)与一次性密码本(One-Time Pad，OTP)算法组合用于生成随机数密钥，结果表明文章编号：2095-4980（2022）05-0492-06
收稿日期：2020-03-26；修回日期：2020-09-10
基金项目：宿迁市科技资助项目(S201819)
*通信作者：管致锦email:****************
第5期卫丽华等：可逆线性同余随机数发生器OTP 与LCG 的组合，算法更快。Bertrand Teguia [6]提出了一种基于素数分布的算法随机整数发生器，是一种新型分布的随机数发生器。然而，关于随机数发生器的可逆方面很少被研究或考虑。在仿真系统运行时，若要回溯至之前某一时刻的场景，就必须恢复和该场景相关的所有数据。目前较通用的做法是使用Checkpointing 技术[7-8]预先保存相关数据，但这种方法会使得系统内存消耗和访存操作随着数据量的增大而急剧上升。Permulla [9]在粒子碰撞的仿真实验中首次使用可逆计算恢复碰撞前的粒子状态，实验结果表明该方法在数据密集且内存紧张的场景下在时间性能和空间性能上均优于Checkpointing 技术。如何可逆地恢复随机数是将可逆计算应用于仿真系统的关键问题之一，仿真系统中涉及的基于各种概率分布的随机数均以均匀分布随机数为基础，本文拟设计一种可逆线性同余随机数发生器(Reversible Linear Congruential Generator ，RLCG)，该随机数发生器对其生成的随机数序列既可正向遍历，又可反向遍历，且反向遍历无需额外内存开销。
1线性同余随机数发生器
线性同余随机数发生器利用数论中的同余运算产生随机数，其递推公式为：
ìíîïïx n =()ax n -1+c mod M r n =x n /M  n =1 2  (1)
式中：a 为乘子，0<a <M ；c 为增量，0≤c <M ；M 为模数，M >0，通常取2的整数次幂；x 0为种子，0≤x 0<M ；为满足较好的统计性质，a 和M 以及c 和M 均互质。通常用表达式LCG(M ,a ,c ,x 0)表示上述随机数发生器，该随机数发生器的周期和统计性质由M 、a 和c 这3个参数所决定，在这方面已经有很多研究[9]。本文将重点关注如何在不影响统计性质的基础上实现可逆线性同余随机数发生器，并用LCG(M ,a ,c ,x 0)表示可逆发生器。
2可逆线性同余随机数发生器（RLCG ）
目前各类编程语言函数库中提供的LCG 实现均只有正向功能，即只能根据当前随机数生成下一个随机数，而不能恢复之前的随机数，因此这些LCG 实现不能应用于可逆环境中。以下将提供两种RLCG 的实现，分别命名为RLCG1和RLCG2。
2.1RLCG1的实现
实现RLCG 的关键是到函数f (x ):x n =(ax n -1+c )
mod M 的逆函数f -1(x )。为到该反函数，首先列出几个有关线性同余方法的定义和定理。定义1
若M |a -b ，即a -b =kM ，则称a 模M 同余b ，记作a ºb (mod M )。a ,b 为整数，M 为正整数。定理1
令M 为正整数，若a ºb (mod M )，c ºd (mod M )，则a +c ºb +d (mod M )且ac ºbd (mod M )。定理2
若a 和M 是互质的整数，则存在整数s ，使得sa º1(mod M )，将s 称为a 对模M 的逆，记作a ˉ。根据以上定理，可以推导出引理1。引理1
若a 和M 互质，函数f (x ):x n =(ax n -1+c )mod M 的反函数f -1(x)为：x n -1=b (x n -c )
mod M ，且b =a ˉmod M ，其中a ˉ为a 对模M 的逆。证明：x n =(ax n -1+c )mod M Þ定义1x n ºax n -1+c (mod M )
Þ定理1x n -c ºax n -1(mod M )Þ定理1a
ˉ(x n -c )ºa ˉax n -1(mod M )Þ定理2a ˉ(x n -c )ºx n -1(mod M )Þ定理1
b (x n -
c )ºx n -1(mo
d M )Þ定义1x n -1=b (x n -c )mod M
可以使用扩展欧几里得算法求解上式中的a
ˉ。RLCG1的Java 实现如程序1所示。程序1中next()函数生成正向随机数，和传统LCG 算法完全一
样；previous()函数用来反向恢复随机数，其中的表达式和引理1中的反函
数公式略有出入，这是由于Java 中允许取余结果为负，而LCG 中要求余
493
太赫兹科学与电子信息学报第20卷数非负；exGCD()函数通过递归的方式实现扩展欧几里得算法以
求解a
ˉ。生成长度为n 的随机数序列其时间开销为O (n )，空间开销为O
(1)。从程序1可见，next()函数和previous()函数的复杂度相同，因
此在RLCG1中反向恢复随机数和正向生成随机数具备相同的时空开
销，其时空复杂度曲线如图1所示。
2.2RLCG2的实现
RLCG1只能根据当前随机数依次恢复前驱随机数，即如要得到
位于当前随机数前n 个位置的随机数，须连续调用n 次previous()函
数，为实现跳跃式恢复前面任一位置的随机数须考虑另一种方法，
如到随机数序列中任一随机数的通项公式。定理3
matlab生成随机数若a ,b 以及M 均为正整数，则等式(a *b )mod M =((a mod M )*(b mod M ))mod M 和(a +b )mod M =(a mod M +b mod M )mod M 恒成立。引理2
已知x n =(ax n -1+c )mod M ，则可推出x n =(a n x 0+(1+a + +a n -1)c )
mod M  n =1 2  。其中，a ,b 及M 均为正整数。证明
x n =(ax n -1+c )mod M Þ存在整数k  使得x n +k n M =ax n -1+c ，且0≤x n <M Þ存在整数k ，
使得x n -ax n -1=c -k n M  n =1 2  Þìíîïïïïïïx 1-ax 0=c -k 1M ()1x 2-ax 1=c -k 2M ()2  x n -1
-ax n -2=c -k n -1M ()n -1x n -ax n -1=c -k n M
()n 将(1)´a n -1 (2)´a n -2 (3)´a n -3  (n -1)´a ，：Þìíîïïïïïïa n -1x 1-a n x 0=a n -1c -a n -1k 1M ()1a n -2x 2-a n -1x 1=a n -2c -a n -2k 2M ()2  ax n -1-a 2x n -2=ac -ak n -1M ()n -1x n -ax n -1=c -k n M ()
n ，将(1)+(2)+…+(n −1)+(n )得：Þx n -a n x 0=(1+a + +a n -1)c -(
k n +ak n -1+ +a n -1k 1)M Þx n +(k n +ak n -1+ +a n -1k 1)M =a n x 0+(1+a + +a n -1)
c 等式两边同时对M 作取余运算：Þ0≤x n <M x n =(a n x 0+(1+a + +a n -1)c )mo
d M
显然，引理2所提供的公式仅需一个位置信息n 就能够计算出随机
数序列中的任何一个数。引理2为跳跃式恢复之前任一位置的随机数
提供了可能，但由于LCG 公式中的a 一般为非常大的数，当n 也较大
时直接计算该式很容易生成溢出，从而导致出现错误的结果。根据定
理3上述公式可以归结为当a 和n 较大时如何求的问题，使用同余幂算
法可以很好地解决该问题。RLCG2的JAVA 实现如程序2所示。
如程序2所示，next()用以正向生成随机数，除了每次调用都要更
新位置n 外与RLCG1的next()函数相同；previous(i)函数用以恢复领先当
前i 个位置的随机数；calNth(n)根据引理2的公式计算第n 个随机数；
modExp()函数是同余幂算法的实现，用以当a 和n 较大时求a n mod M 的
问题。RLCG2恢复随机数的时空复杂度如图2所示，可见虽然RLCG2
可以跳跃式地恢复之前的随机数，但其时间性能却比RLCG1采用依次
恢复的方式差，尤其当待恢复的随机数在序列中位置靠后时，这种差
异将越发明显。Fig.1Time -space complexity curve for RLCG1recovering random numbers 图1RLCG1恢复随机数的时空复杂度曲线
mul=(mul+modExp (a , i , M ))% M ;  }    …      }  } 程序2  RLCG2的Java 实现关键代码 public class RLCG2 { //正向生成随机数 public long next(){ n =n +1; x =(a *x +c )%M ; return x ;  } //恢复领先当前i 个位置的随机数 public long previous (long i ){ n =n -i ; x =calNth (n ); return x ;  } //计算第n 个随机数 private long calNth (long n ){ long mul=1; for (long i =1; i <n ; i ++){ x =(modExp (a , n , M )*(x 0 % M ))% M ; x =(x +(mul*c )% M )% M ; return x ;  } //同余冪算法 private long modExp (long base, long exp, long M){ 494
第5期卫丽华等：可逆线性同余随机数发生器3基于CDF 的可逆随机数发生器
为适应各种仿真环境对随机数不同分布的需求，利用累计分布函数(Cumulative Distributions Function ，CDF)在闭区间内是可逆的特性，可以较容易地将RLCG 生成的均匀分布的随机数列映射到所需的分布。给定PDF 函
数p ()对应的CDF 函数c p ()，可将分布采样为x r =c -1p (r )，其中r 是RLCG 生成的均匀分布随机数，且r Î[0 1
]。下面以生成指数分布的可逆随机数为例。假设给定指数分布概率密度函数(Probability Density Function ，PDF)如下所示：
p (x )={λe -λx  x ≥00 x <0
得到累计分布函数CDF ：c p (x )={1-e -λx  x ≥00 x <0
求得逆累计分布函数CDF ：c -1p
(r )=x r =ìíî
ïï-log(1-r )λ=-log r λ r Î[0 1]0生成任意分布的可逆随机数生成算法如表1所示。其中R u (),R u −1()为RLCG 正反函数，c -1p (r )为累计分布函数CDF 的反函数。4RLCG 的验证和比较以LCG(232,22695477,1,0)为例，对RLCG1和RLCG2的可逆性
以及时空性能进行验证，实验平台的主要配置如下：Intel i7-4710HQ
CPU 2.5GHZ ，8G RAM 。
4.1可逆性的验证
通过RLCG1和RLCG2的next ()函数分别生成50个随机数，可发现生成的随机数序列相同，如图3(a)所示。然后，通过两者的previous ()函数恢复之前的随机数，恢复的随机数序列同样相同，如图3(b)所示。可发现图3和图4严格对称，说明RLCG1和RLCG2都正确地实现了可逆生成和恢复随机数的目的。
表1基于CDF 的可逆随机数发生器Table 1CDF-based reversible random number generator
positive
R c ():
r<-R u ()
x r <-c p -1(r )
return x r reverse R c -1():r<-R u -1()x r <-c p -1(r )return x
r Fig.2Time -space complexity curve for RLCG2recovering random numbers
图2RLCG2
恢复随机数的时空复杂度曲线
Fig.3RLCG1and RLCG2generating random number sequences
图3RLCG1和RLCG2生成随机数序列495
太赫兹科学与电子信息学报第20卷
4.2性能的验证
为验证RLCG1和RLCG2的时空性能，将其与使用Checkpointing 技术实现的RLCG 算法进行时空性能的比较，分别使用RLCG1、RLCG2和Checkpointing 的next ()函数依次生成由30000个随机数组成的随机数序列，以序列中位置是1000整数倍的随机数时间为采样点，其时间性能比较如图4所示，可发
现正向生成随机数时RLCG1和RLCG2在时间消耗上优于Checkpointing ，这是由于Checkpointing 在每次生成随机数时需要额外的时间将该随机数存入堆栈以便后续恢复。
分别使用RLCG1、RLCG2和Checkpointing 的previous()函数依次恢复由next ()函数生成的30×103个随机数组成的序列，其时间性能比较如图5所示，可见Checkpointing 略优于RLCG1，而RLCG2在恢复序列中位置为29×103~30×103的103个随机数时耗时较多，为2.97s ，是其他采样点时间的103倍，这和RLCG2的算法分析相符，即位置在序列中越靠后其耗时就越长，但当恢复的数据位置逐渐靠前时开始优于Checkpoingting ，并逐渐接近RLCG1。
至于RLCG1、RLCG2和Checkpointing 对内存的消耗，从3种不同实现的代码即可分析出，RLCG1仅需一个变量x 保存当前随机数；RLCG2不仅需要变量x 保存当前随机数，还需要一个变量n 存储当前随机数在序列中的位置；前两者对内存的消耗是常量级的，而Checkpointing 需要保存每一个生成的随机数，因此对内存的消耗随着随机数序列长度而线性增长，如图6所示。
5结论
从实验结果可知，RLCG1在生成随机数时其时间性能优于Checkpointing ，在恢复随机数时其时间性能接近Checkpointing ，且在内存开销上随着随机数序列的增长明显优于Checkpointing ，同时通过累计分布函数的反函数，将生成的均匀随机数转换为任意分布随机数，且保持可逆性。因此在数据密集
型仿真环境中恢复系统场景时可使用本文提出的可逆随机发生器恢复相应的随机参数，满足不同场景需求，具有较高的实践指导意义。参考文献：
[1]苏耀鑫，高秀峰.基于矩阵的无线传感器网络SNEP 改进[J ].太赫兹科学与电子信息学报,2018,16(6):1072-1079.(SU
Yaoxin,GAO Xiufeng.Research on improvement of SNEP protocol based on matrix [J ].Journal of Terahertz Science and Electronic Information Technology,2018,16(6):1072-1079.)
[2]
CLAWDIA J,KHAIRINA N,HARAHAP M K.Implementasi algoritma kriptografi One Time Pad(OTP)dengan dyamic key Linear Congruential Generator(LCG)[J ].KOMIK(Konferensi Nasional Teknologi Informasi dan Komputer),2017,1(1):12-14.[3]
MISHRA M,MANKAR V.Text encryption algorithms based on pseudo -random number generator [J ].International Journal of Computer Applications,2015,111(2):1-6.[4]SOKOUTI M,SOKOUTI B,PASHAZADEH S,et al.Genetic -based random key generator(GRKG):a new method for generating
more -random keys for one -time pad cryptosystem [J ].Neural Computing and Applications,
2013:1667-1675.Fig.4Forward time performance comparison
图4
正向时间性能比较
Fig.5Reverse time performance comparison
图5
反向时间性能比较Fig.6Space performance comparison 图6空间性能比较
496

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。