Uniform random number generation

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. In this paper, we examine practical ways of generating (deterministic approximations to) such uniform variates on a computer. We compare them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. We look in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and show how all of them can be analyzed in terms of their lattice structure. We also mention other classes of generators, like non-linear generators, discuss other kinds of theoretical and empirical statistical tests, and give a bibliographic survey of recent papers on the subject.     

基于伪随机排列的密码模型及其在MATLAB中的实现

给出了关于密码编码学的一般数学模型,在此基础上提出了一种新颖的能用于中文文稿加密的实用有效的编码方法:基于伪随机排列的密码模型(PRP算法),并在MATLAB中实现了上述模型.通过唯密文攻击和已知明文攻击的密码分析,得知该算法具有很强的抵抗攻击能力.     

Gowers norms and pseudorandom measures of subsets

Let $A \subset {{\Bbb Z}_N}$, and ${f_A}(s) = \left\{ {\begin{array}{*{20}{l}}{1 - \frac{{|A|}}{N},}&{{\rm{for}}\;s \in A,}\\{ - \frac{{|A|}}{N},}&{{\rm{for}}\;s \notin A.}\end{array}} \right.$ We define the pseudorandom measure of order k of the subset A as follows, P_k(A, N) = $\begin{array}{*{20}{c}}{\max }\\D\end{array}$|$\mathop \Sigma \limits_{n \in {\mathbb{Z}_N}}$f_A(n + c₁)f_A(n + c₂) … f_A(n + c_k)|, where the maximum is taken over all D = (c₁, c₂, . . . , c_k) ∈ ${\mathbb{Z}^k}$ with 0 ≤ c₁ < c₂ < … < c_k ≤ N - 1. The subset A ⊂ ${{\mathbb{Z}_N}}$ is considered as a pseudorandom subset of degree k if P_k(A, N) is “small” in terms of N. We establish a link between the Gowers norm and our pseudorandom measure, and show that “good” pseudorandom subsets must have “small” Gowers norm. We give an example to suggest that subsets with “small” Gowers norm may have large pseudorandom measure. Finally, we prove that the pseudorandom subset of degree L(k) contains an arithmetic progression of length k, where L(k) = 2·lcm(2, 4, . . . , 2|$\frac{k}{2}$|), for k ≥ 4, and lcm(a₁, a₂, . . . , a_l) denotes the least common multiple of a₁, a₂, . . . , a_l.     

蒙特卡罗模拟中相关变量随机数序列的产生方法

蒙特卡罗模拟有时需要对多维相关随机变量进行模拟抽样．本文介绍基于Choesky因子线性变换一非线性变换产生具有指定边缘分布和相关系数的多维相关随机变量抽样序列的一般方法,给出一种简单易行的高效数值实现途径和一些模拟结果．模拟结果表明,该方法产生的各随机变量抽样序列间具有预期要求的相关性,并能通过指定边缘分布Kolmogorov—Smimov非参数假设检验．对该方法应用中的一些限制问题进行了讨论．     

1‐Factorizations of pseudorandom graphs

A 1‐factorization of a graph G is a collection of edge‐disjoint perfect matchings whose union is E(G). In this paper, we prove that for any ?>0, an (n,d,λ)‐graph G admits a 1‐factorization provided that n is even, C₀ ≤ d ≤ n?1 (where C₀=C₀(?) is a constant depending only on ?), and λ ≤ d^1??. In particular, since (as is well known) a typical random d‐regular graph G_n,d is such a graph, we obtain the existence of a 1‐factorization in a typical G_n,d for all C₀ ≤ d ≤ n?1, thereby extending to all possible values of d results obtained by Janson, and independently by Molloy, Robalewska, Robinson, and Wormald for fixed d. Moreover, we also obtain a lower bound for the number of distinct 1‐factorizations of such graphs G, which is better by a factor of 2^nd/2 than the previously best known lower bounds, even in the simplest case where G is the complete graph.     

All-optical pseudorandom binary sequence generator with TOAD-based D flip-flops

An all-optical pseudo random binary sequence (PRBS) generator is designed using serially interconnected discrete Terahertz Optical Asymmetric Demultiplexer (TOAD)-based D flip-flops in a configuration exactly like the standard electronic setup. The performance of the circuit is evaluated through numerical simulation, which confirms its feasibility in terms of the choice of the critical parameters. The proposed scheme has been theoretically demonstrated for a 3-bit and 7-bit degree PRBS but can be extended to higher order by means of additional TOAD-based D flip-flops. Thus it can constitute an efficient solution for implementing all-optically a PRBS in an affordable, controllable and realistic manner.     

Unconventional Coding Technique Applied to Multi-Level Polarization Modulation

A new technique is proposed to improve information confidentiality in optical-fiber communications without bandwidth consumption. A pseudorandom vectorial sequence was generated by a dynamic system algorithm and used to codify a multi-level polarization modulation based on the Stokes vector. Optical-fiber birefringence, usually considered as a disturbance, was exploited to obfuscate the signal transmission. At the receiver end, the same pseudorandom sequence was generated and used to decode the multi-level polarization modulated signal. The proposed scheme, working at the physical layer, provides strong information security without introducing complex processing and thus latency.     

大族长度为pq的伪随机k元序列

Mauduit与Sárkzy在一系列论文中研究了κ元序列的伪随机性.本文通过对模pq剩余类环Z_(pq)进行分割,进而结合离散对数的方法,构造了一大族长度为pq的伪随机κ元序列,并证明其具有很好的伪随机性.     

Ultra-high speed all-optical shift registers and their applications in OTDM networks

All-optical shift registers are basic building modules for the development of ultra-high speed optical time division multiplexing networks. In this paper, we review the progress that has been made in this cutting-edge technology, focusing on implementations that exploit the attractive features of semiconductor optical amplifier (SOA)-based interferometric configurations. We present regenerative storage performed with an all-optical recirculating shift register with an inverter at 10 Gb/s using a SOA-assisted Sagnac switch and a second SOA to provide feedback. We demonstrate also an all-optical memory based on the SOA-assisted Ultrafast Nonlinear Interferometer capable of reading/writing 20 Gb/s packets of variable length without data inversion. These registers can find application in the development of two nontrivial complex all-optical circuits of enhanced functionality. The first is an all-optical pseudorandom binary sequence generator for which we describe an efficient design algorithm and propose ways for monitoring and verification. The second is an all-optical error counter for which we address the error detection and evaluation issues using a novel sampling technique. These circuits are key elements for the implementation of a high-speed, all-optical bit error rate tester (BERT), which has the potential to outperform its electronic equivalent and constitute a possible new product for the telecommunications industry.     

A complexity measure for families of binary sequences

In earlier papers finite pseudorandom binary sequences were studied, quantitative measures of pseudorandomness of them were introduced and studied, and large families of “good” pseudorandom sequences were constructed. In certain applications (cryptography) it is not enough to know that a family of “good” pseudorandom binary sequences is large, it is a more important property if it has a “rich”, “complex” structure. Correspondingly, the notion of “f-complexity” of a family of binary sequences is introduced. It is shown that the family of “good” pseudorandom binary sequences constructed earlier is also of high f-complexity. Finally, the cardinality of the smallest family achieving a prescibed f-complexity and multiplicity is estimated. This revised version was published online in August 2006 with corrections to the Cover Date.