A quasi-random number generator with infinite period

An aperiodic quasi-random number generator is constructed.     

A new random number generator from permutation groups

We describe a new random number generator, RPGM, which is based on the cryptographic system PGM invented by Magliveras in 1976 and subsequently studied by Magliveras and Surkan [10]. PGM relies on a certain method of machine representation for permutation groups. This method allows for encryption and decryption algorithms based on a space-efficient data structure which is called a logarithmic signature for the group. The efficacy of RPGM is studied by means of an extensive analysis of generated data of 100,000 numbers using the Mathieu groupM ₂₄ in its 5-transitive representation on 24 points.     

Combined random number generator via the generalized Chinese remainder theorem

The combined random number (RN) generator has been considered by many scholars as a good RN generator. One promising type of combined RN generator, recommended by L'Ecuyer (Oper. Res. 44 (1996) 816; 47 (1999) 159), is the combined multiple recursive generator (MRG). This paper analyzes the combined MRG via the Chinese remainder theorem. A new combined generator based on the generalized Chinese remainder theorem and on the Ore algorithm (Amer. Math. Monthly 59 (1952) 365) is presented. The proposed combined generator improves the combined MRG in terms of both the suitability for various types of RN generators and the restriction on the moduli of the individual generators. Therefore, the proposed combined generator is an ideal RN generator and is most recommended.     

Spectrum and entropy of C-systems MIXMAX random number generator

The uniformly hyperbolic Anosov C-systems defined on a torus have very strong instability of their trajectories, as strong as it can be in principle. These systems have exponential instability of all their trajectories and as such have mixing of all orders, nonzero Kolmogorov entropy and a countable set of everywhere dense periodic trajectories. In this paper we are studying the properties of their spectrum and of the entropy. For a two-parameter family of C-system operators A(N, s), parameterised by the integers N and s, we found the universal limiting form of the spectrum, the dependence of entropy on N and the period of its trajectories on a rational sublattice. One can deduce from this result that the entropy and the periods are sharply increasing with N. We present a new three-parameter family of C-operators A(N, s, m) and analyse the dependence of its spectrum and of the entropy on the parameter m. We are developing our earlier suggestion to use these tuneable Anosov C-systems for multipurpose Monte-Carlo simulations. The MIXMAX family of random number generators based on Anosov C-systems provide high quality statistical properties, thanks to their large entropy, have the best combination of speed, reasonable size of the state, tuneable parameters and availability for implementing the parallelisation.     

A novel dynamic model of pseudo random number generator

An interesting hierarchy of random number generators is introduced in this paper based on the review of random numbers characteristics and chaotic functions theory. The main objective of this paper is to produce an ergodic dynamical system which can be implemented in random number generators. In order to check the efficacy of pseudo random number generators based on this map, we have carried out certain statistical tests on a series of numbers obtained from the introduced hierarchy. The results of the tests were promising, as the hierarchy passed the tests satisfactorily, and offers a great capability to be employed in a pseudo random number generator.     

Pseudo random number generator based on quantum chaotic map

For many years dissipative quantum maps were widely used as informative models of quantum chaos. In this paper, a new scheme for generating good pseudo-random numbers (PRNG), based on quantum logistic map is proposed. Note that the PRNG merely relies on the equations used in the quantum chaotic map. The algorithm is not complex, which does not impose high requirement on computer hardware and thus computation speed is fast. In order to face the challenge of using the proposed PRNG in quantum cryptography and other practical applications, the proposed PRNG is subjected to statistical tests using well-known test suites such as NIST, DIEHARD, ENT and TestU01. The results of the statistical tests were promising, as the proposed PRNG successfully passed all these tests. Moreover, the degree of non-periodicity of the chaotic sequences of the quantum map is investigated through the Scale index technique. The obtained result shows that, the sequence is more non-periodic. From these results it can be concluded that, the new scheme can generate a high percentage of usable pseudo-random numbers for simulation and other applications in scientific computing.     

A multiple recursive non-linear congruential pseudo random number generator

On-linear multiple recursive congruential pseudo random number generator with prime modulus p is introduced. Let x, n0, be the sequence generated by a usual linear (r+1)-step recursive congruential generator with prime modulus p and denote by N(n), n0, the sequence of non-negative integers with x_N(n)0 (mod p). The non-linear generator is defined by z_nx_N(n)+1·x _N(n) ^–1 (mod p), n0, where x _N(n) ^–1 denotes the inverse element of x_N(n) in the Galois field GF(p). A condition is given which ensures that the generated sequence is purely periodic with period length p^r and all (p–1)^r r-tupels (y₁,...,y_r) with 1y₁,...,y_rp are generated once per period when r-tupels of consecutive numbers of the generated sequence are formed. For r=1 this generator coincides with the generator introduced by Eichenauer and Lehn [2].     

The additive congruential random number generator—A special case of a multiple recursive generator

This paper considers an approach to generating uniformly distributed pseudo-random numbers which works well in serial applications but which also appears particularly well-suited for application on parallel processing systems. Additive Congruential Random Number (ACORN) generators are straightforward to implement for arbitrarily large order and modulus; if implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.     

A true random number generator based on mouse movement and chaotic cryptography

True random number generators are in general more secure than pseudo random number generators. In this paper, we propose a novel true random number generator which generates a 256-bit random number by computer mouse movement. It is cheap, convenient and universal for personal computers. To eliminate the effect of similar movement patterns generated by the same user, three chaos-based approaches, namely, discretized 2D chaotic map permutation, spatiotemporal chaos and “MASK” algorithm, are adopted to post-process the captured mouse movements. Random bits generated by three users are tested using NIST statistical tests. Both the spatiotemporal chaos approach and the “MASK” algorithm pass the tests successfully. However, the latter has a better performance in terms of efficiency and effectiveness and so is more practical for common personal computer applications.     

The golden number and Fibonacci sequences in the design of voting structures

Some distinguished types of voters, as vetoes, passers or nulls, as well as some others, play a significant role in voting systems because they are either the most powerful or the least powerful voters in the game independently of the measure used to evaluate power. In this paper we are concerned with the design of voting systems with at least one type of these extreme voters and with few types of equivalent voters. With this purpose in mind we enumerate these special classes of games and find out that its number always follows a Fibonacci sequence with smooth polynomial variations. As a consequence we find several families of games with the same asymptotic exponential behavior except for a multiplicative factor which is the golden number or its square. From a more general point of view, our studies are related with the design of voting structures with a predetermined importance ranking.     

Asymptotic number of isometric generalized Fibonacci cubes

For a binary word f, let Q_d(f) be the subgraph of the d-dimensional cube Q_d induced on the set of all words that do not contain f as a factor. Let G_n be the set of words f of length n that are good in the sense that Q_d(f) is isometric in Q_d for all d. It is proved that lim_n→∞|G_n|/2ⁿ exists. Estimates show that the limit is close to 0.08, that is, about eight percent of all words are good.     

The chromatic number of random graphs

For a fixed probabilityp, 0<p<1, almost every random graphG _n,p has chromatic number $$\left( {\frac{1}{2} + o(1)} \right)\log (1/(1 - p))\frac{n}{{\log n}}$$ ,     

The chromatic number of random graphs

Let χ(G(n, p)) denote the chromatic number of the random graphG(n, p). We prove that there exists a constantd ₀ such that fornp(n)>d ₀,p(n)→0, the probability that $$\frac{{np}}{{2 log np}}\left( {1 + \frac{{\log log np - 1}}{{\log np}}} \right)< \chi (G(n,p))< \frac{{np}}{{2 log np}}\left( {1 + \frac{{30 \log \log np}}{{\log np}}} \right)$$ tends to 1 asn→∞.     

The concentration of the chromatic number of random graphs

We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n ^–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n ) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship.     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

The chromatic number of random Borsuk graphs

We study a model of random graph where vertices are n i.i.d. uniform random points on the unit sphere S^d in , and a pair of vertices is connected if the Euclidean distance between them is at least 2??. We are interested in the chromatic number of this graph as n tends to infinity. It is not too hard to see that if ?>0 is small and fixed, then the chromatic number is d+2 with high probability. We show that this holds even if ?→0 slowly enough. We quantify the rate at which ? can tend to zero and still have the same chromatic number. The proof depends on combining topological methods (namely the Lyusternik–Schnirelman–Borsuk theorem) with geometric probability arguments. The rate we obtain is best possible, up to a constant factor—if ?→0 faster than this, we show that the graph is (d+1)‐colorable with high probability.25     

The game chromatic number of random graphs

Given a graph G and an integer k, two players take turns coloring the vertices of G one by one using k colors so that neighboring vertices get different colors. The first player wins iff at the end of the game all the vertices of G are colored. The game chromatic number χ_g(G) is the minimum k for which the first player has a winning strategy. In this study, we analyze the asymptotic behavior of this parameter for a random graph G_n,p. We show that with high probability, the game chromatic number of G_n,p is at least twice its chromatic number but, up to a multiplicative constant, has the same order of magnitude. We also study the game chromatic number of random bipartite graphs. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008