Empirical tests of the intrinsic pseudorandom number generator on IBM-compatible microcomputers

This paper reports results of frequency and serial correlation tests, for 30 different seeds and two different seeding mechanisms (the RANDOMIZE statement and the RND function), of a Microsoft pseudorandom number generator available on IBM-compatible (and some IBM) microcomputers. The generator is shown to perform well on these screening tests, in comparison to previously reported results for the Microsoft generator available on IBM-PC microcomputers. However, the generator seeding mechanisms--the RANDOMIZE statement and the RND function--exhibit anomalies similar to those of the IBM-PC generator, and could result in seeding which is inconsistent with the desire of the user. Furthermore, the differences in the randomness characteristics of sequences of numbers generated by IBM and IBM-compatible microcomputers have serious implications regarding the true compatibility of the two types of microcomputers.     

The importance of proper seeding of the Applesoft pseudorandom number generator

The popularity of the use of Apple II/IIe hardware in medical applications is evidenced by the variety of articles devoted to the use of this hardware in biomedical research and medical practice. Many of these applications are of a stochastic nature, including simulations, and depend on the Applesoft random number generator. Unfortunately, the Applesoft generator has exhibited a number of flaws, including lack of uniformity of generated sequences of numbers, and serial correlation within such sequences. This paper provides evidence of these problems for a variety of seeds, and provides suggestions for acceptable seeds which ensure that the generated sequences of numbers pass two fundamental statistical tests for randomness.     

基于超多核心平台的Knuth39并行化实现及性能分析

针对Knuth39随机数发生器运行速度慢的问题,提出了一种基于超多核心(MIC)平台的Knuth39并行化方法.首先,将Knuth39发生器的随机数序列以固定间隔划分成多个子序列;然后,每个线程从各子序列的起点开始生成随机数;最后,将各个线程生成的随机数序列组合成最终的序列.实验结果表明,并行化后Knuth39通过了TestU01的452项测试,与串行程序相同.同中央处理器(CPU)单线程相比,并行化后MIC平台下的最优加速比可达到15.69倍.所提方法有效地提高了Knuth39发生器的运行速度,并且保证了生成序列的随机性,更加适用于高性能计算领域.     

Compound cubic congruential pseudorandom numbers

Nonlinear congruential methods for generating uniform pseudorandom numbers show several attractive properties. The present paper deals with a particularly simple compound approach, which is based on cubic permutation polynomials over finite fields. These pseudorandom number generators allow a fast (and parallelized) implementation in single precision. Statistical independence properties of the generated sequences are studied. An upper bound for the discrepancy of tuples of successive pseudorandom numbers is established, which rests on a classical result of A. Weil on exponential sums. Finally, a ready-to-program example of a compound cubic congruential generator is given.     

线性乘同余法在购车摇号中的应用

目前线性乘同余(linear multiplicative congruential method，LMCM)随机数发生器被广泛使用于购车摇号中。为改善该发生器对购车摇号申请编码分配与摇号编号中签序列的统计品质，基于均匀分配理念，针对应用需求设计了一种新的线性乘同余算法。在新算法中，以原线性乘同余发生器中的模数为基础，通过相同种子数平均分配构造产生随机数；由于算法分段实现，使得随机数的产生在计算量上不会有明显的增加，能满足购车摇号所需。而统计检验的结果表明，该算法对随机序列的统计品质改善是显著的；同时，算法已成功运用于贵阳市小客车专段号牌摇号中，具有很好的应用推广性，是一种新的随机数抽样算法。     

基于时空混沌的伪随机数发生器设计

时空混沌系统有很好的密码学特性,但目前基于该模型提出的伪随机数发生器存在效率不高的问题。为此,提出了一种高效的基于时空混沌的伪随机数设计方案。在产生伪随机数的过程中,将一些耗时操作尽可能地替换为一些快速操作,并尽可能地减少时空混沌模型自身的迭代次数,因此算法的效率得到有效提升。对算法所产生的伪随机序列的密码学属性进行了测试,结果表明该伪随机发生器方案不仅运算速度快,而且具有很好的密码学性能。     

Generating parallel quasirandom sequences via randomization

Quasi-Monte Carlo (QMC) methods are now widely used in scientific computation, especially in estimating integrals over multidimensional domains. One advantage of QMC is that it is easy to parallelize applications, and so the success of any parallel QMC application depends crucially on the quality of parallel quasirandom sequences used. Much of the recent work dealing with parallel QMC methods has been aimed at splitting a single quasirandom sequence into many subsequences. In contrast with this perspective to concentrate on breaking one sequence up, this paper proposes an alternative approach to generating parallel sequences for QMC. This method generates parallel sequences of quasirandom numbers via scrambling. The exact meaning of scrambling depends on the type of parallel quasirandom numbers. In general, we seek to randomize the generator matrix for each quasirandom number generator. Specifically, this paper will discuss how to parallelize the Halton sequence via scrambling. The proposed scheme for generating parallel random number streams is especially good for heterogeneous and unreliable computing environments.     

基于Galois线性反馈移位寄存器的随机数产生

随着FPGA计算能力的不断提高,使用FPGA进行计算加速的研究越来越多。在这些加速对象中,有许多应用都需要使用到随机数生成器。本文应用Leap Forward方法,提出了一种基于Galois类型线性反馈移位寄存器产生随机数的硬件结构。详细分析了该硬件结构中转换矩阵的特征,给出了提高工作速度和减小硬件面积的方法。应用该硬件结构,本文在Xilinx Vertex 6 FPGA上设计实现了16位输出的随机数产生器。实验结果显示,该随机数产生器仅使用了6个slices资源,工作速度可以达到951MHz,产生随机数的吞吐率可以达到15.2Gbps。文中使用K-S方法对所产生随机数的质量进行了检测,并给出了所产生的105个随机数的CDF曲线与理论CDF的比对结果。     

基于LFSR的演化随机序列发生器

针对基于线性反馈移位寄存器的随机序列发生器产生的随机数线性复杂度低的问题,设计一个新的随机序列发生器,使用遗传算法演化线性反馈移位寄存器产生的随机序列,新产生的序列可以通过SP800—22的测试。测试结果表明,生成的序列周期大、线性复杂度高,能够满足安全协议和密码算法的安全强度要求。     

Application of Halton's sequences in the Monte-Carlo method

Uniformly distributed Halton sequences are compared with the pseudorandom number sequences generated by a standard congruential generator.Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 176–179, September–October, 1992.     

基于MT发生器的车辆生成模型构建与仿真

针对交通流仿真技术中广泛使用的线性同余发生器在周期长度和随机性方面的不足,引入MT随机数发生器,通过性能评价验证其优越性,然后在空闲和拥挤两种交通状态下,基于MT发生器产生的随机数,应用不同的随机分布构建相应的随机发车模型。在VC环境下开发车辆生成程序进行仿真实验,将仿真数据与实测数据进行对比分析,结果表明,基于MT发生器的随机发车模型更好地逼近了实际交通状态。     

Yet another application of the Monte Carlo method for modeling in the field of biomedicine

By means of Monte Carlo simulations performed in the C programming language, an example of scientific programming for the generation of pseudorandom numbers relevant to both teaching and research in the field of biomedicine is presented. The relatively simple algorithm proposed makes possible the statistical analysis of sequences of random numbers. The following three generators of pseudorandom numbers were used: the rand function contained in the stdlib.h library of the C programming language, Marsaglia's generator, and a chaotic function. The statistical properties of the sequences generated were compared, identical parameter values being adopted for this purpose. The properties of two estimators in finite samples of the pseudorandom numbers were also evaluated and, under suitable conditions, both the maximum-likelihood and method of moments proved to be good estimators. The findings demonstrated that the proposed algorithm appears to be suitable for the analysis of data from random experiments, indicating that it has a large variety of possible applications in the clinical practice.     

新的基于D-序列的随机数产生器

针对现有随机数产生器计算消耗大和占用空间多的问题,提出了一种新的基于D-序列的随机数序列产生器。通过在现有D-序列的产生过程中引入随机变量来产生更长的任意进制的新的随机D-序列。它不仅继承了原有D-序列结构简单,计算复杂度低,存储需求少和随机特性好的特点。还克服了原有D-序列长度有限的运用限制。通过自相关性、互相关性和概率分布分析证明了该新D-序列的随机特性比现有D-序列更优良。这些特性使它比现有的其他复杂随机数产生器(如混沌随机数产生器和硬件随机数产生器)更适合于具有节点计算能力有限,存储空间有限和能量有限的无线传感网络。     

Period analysis of the Logistic map for the finite field

Usually, the security of traditional cryptography which works on integer numbers and chaotic cryptosystem which works on real numbers is worthy of study. But the classical chaotic map over the real domain has a disadvantage that the calculation accuracy of the floating point number can be doubled when the map is implemented by computer. This is a serious drawback for practical application. The Logistic map is a classical chaotic system and it has been used as a chaotic cipher in the real number field. This inevitably leads to the degradation of finite precision under computer environment, and it is also very difficult to guarantee security. To solve these drawbacks, we extend the Logistic map to the finite field. In this paper, we consider the Logistic map for the finite field N = 3ⁿ, and analyze the period property of sequences generated by the Logistic map over Z_N. Moreover, we discuss the control parameters which may influence the behavior of the mapping, and show that the Logistic map over Z_N may be suitable for application by performance analysis. Ultimately, we find that there exists an automorphic map between two Logistic maps with the different control parameters, which makes them suitable for sequence generator in cryptosystem. The automorphic sequence generated algorithm based on the Logistic map over Z_N is designed and analyzed in detail. These sequences can be used in the pseudorandom number generator, the chaotic stream cipher, and the chaotic block cipher, etc.     

一种新型均匀分布混沌伪随机数发生器

提出了一种基于一维无限折叠混沌映射的均匀分布混沌伪随机数发生器。统计测试和仿真证实，在一定的参数范围内，所产生的混沌序列为均匀分布序列且具有理想的二值自相关函数。     

超混沌伪随机序列生成器设计与性能分析

在分析了Folded towel映射系统动力学特性的基础上,采用位序列量化算法,设计了一种新型基于离散超混沌映射的伪随机序列生成器。该伪随机序列生成器能同时生成三种伪随机序列,且均通过了NIST SP800-22随机数检验标准测试,具有接近[δ]函数的自相关性和接近于0的互相关性,系统密钥空间大,初值敏感性和复杂度高等特点,适合应用于信息加密。     

A cryptographic checksum for integrity protection

This paper describes a cryptographic checksum technique for verifying the integrity of information in computer systems with no built-in protection. The technique is based on the use of repeated encryption using an cryptosystem as a pseudo-random number generator ( ), the use of a user specified key as a seed for the , and reduction in a pseudo-random modulus as a means for mixing user specified information with generated numbers.     

Security problems for a pseudorandom sequence generator based on the Chen chaotic system

Recently, a novel pseudorandom number generator scheme based on the Chen chaotic system was proposed. In this study, we analyze the security weaknesses of the proposed generator. By applying a brute force attack on a reduced key space, we show that 66% of the generated pseudorandom number sequences can be revealed. Executable C# code is given for the proposed attack. The computational complexity of this attack is O(n), where n is the sequence length. Both mathematical proofs and experimental results are presented to support the proposed attack.     

Designing a pseudorandom bit generator based on LFSRs and a discrete chaotic map

A new method for the generation of pseudorandom numbers, based on two linear feedback shift registers (LFSRs) and a discrete-space chaotic map is presented. The proposed method consists of multiple stages; in stage one a pseudorandom sequence is generated. In stage two a selection of output bits is conducted in order to produce sequences with high randomness. Because many previous methods based on LFSRs and XOR operations are not able to resist chosen and known plaintext attack, stage one of the proposed method is designed to be resistant to this problem. Relations between two LFSRs and the parameters of the chaotic map are established in such a way that based on known output bits of a proposed generator it is impossible to obtain any part of the secret key without guessing the whole secret key. The randomness of generated sequences is confirmed using NIST, TestU01, and the DIEHARD test. The advantages of the proposed method are virtually unlimited key space and resistance to digital degradation.     

Monte Carlo methods in fuzzy linear regression II

We apply our new fuzzy Monte Carlo method to a certain fuzzy linear regression problem to estimate the best solution. The best solution is a vector of crisp numbers, for the coefficients in the model, which minimizes one of two error measures. We use a quasi-random number generator to produce random sequences of these crisp vectors which uniformly fill the search space. We consider an example problem and show this Monte Carlo method obtains the best solution for both error measures.