Inferring sequences produced by a linear congruential generator on elliptic curves missing high-order bits

Let p be a prime and let be an elliptic curve defined over the finite field of p elements. For a given point the linear congruential genarator on elliptic curves (EC-LCG) is a sequence (U _n ) of pseudorandom numbers defined by the relation: where denote the group operation in and is the initial value or seed. We show that if G and sufficiently many of the most significants bits of two consecutive values U _n , U _n+1 of the EC-LCG are given, one can recover the seed U ₀ (even in the case where the elliptic curve is private) provided that the former value U _n does not lie in a certain small subset of exceptional values. We also estimate limits of a heuristic approach for the case where G is also unknown. This suggests that for cryptographic applications EC-LCG should be used with great care. Our results are somewhat similar to those known for the linear and non-linear pseudorandom number congruential generator.      

Re-seeding invalidates tests of random number generators

Kim et al. [C. Kim, G.H. Choe, D.H. Kim, Test of randomness by the gambler’s ruin algorithm, Applied Mathematics and Computation 199 (2008) 195-210] recently presented a test of random number generators based on the gambler’s ruin problem and concluded that several generators, including the widely used Mersenne Twister, have hidden defects. We show here that the test by Kim et al. suffers from a subtle, but consequential error: re-seeding the pseudorandom number generator with a fixed seed for each starting point of the gambler’s ruin process induces a random walk of the test statistic as a function of the starting point. The data presented by Kim et al. are thus individual realizations of a random walk and not suited to judge the quality of pseudorandom number generators. When generating or analyzing the gambler’s ruin data properly, we do not find any evidence for weaknesses of the Mersenne Twister and other widely used random number generators.     

New pseudorandom sequences constructed by quadratic residues and Lehmer numbers

Let be an odd prime. Define

where is the multiplicative inverse of modulo such that . This paper shows that the sequence is a ``good" pseudorandom sequence, by using the properties of exponential sums, character sums, Kloosterman sums and mean value theorems of Dirichlet -functions.

     

On Some Properties of the Shrinking Generator

We obtain several results about the output rate and distribution ofzeros and ones of the shrinking generator associated with two linear recurringsequences. These results are based on various bounds on the number of zeros of linearrecurring sequences. Non-linear recurring sequences are considered aswell.     

Performance enhancement using the bipolar capacity of bipolar coded fiber Bragg gratings and balanced detection in the spectral encoded code-division-multiple-access systems

This paper proposes a performance-enhanced code-division-multiple-access (CDMA) system using modified pseudorandom noise (PN) coded fiber Bragg gratings (FBGs) with a bipolar optical CDMA encoder/decoder. The data were encoded either by a unipolar signature sequence of modified PN code or by its complement, depending on whether the data bit was ‘1’ or ‘0’. Numerical simulation confirmed that bit error rate (BER) performance largely improved due to the increased decision margin at the receiver. Furthermore, at the BER of 10⁻⁹, the tolerance of spectral power distortion in the optical source appeared to be nearly twice that of conventional optical CDMA systems.     

一些新数列的偏差与伪随机性

设p为奇素数,x为整数且满足1≤x≤p-1．定义数列其中■是n模p的乘法逆,满足n■≡1 mod p以及1≤■≤p-1．证明了(x_n)是一致分布数列,(e_n)是好的伪随机数列．这表明在二进制数列与[0,1)数列之间存在某种联系．