From: Mok-Kong Shen <mok-kong.shen@stud.uni-muenchen.de>
Subject: A Simple and Efficient Pseudo-Random Bit Generator
Date: 1998/04/07
Date: 1998-04-07T00:00:00+00:00 [thread overview]
Message-ID: <352A0912.D4839DF3@stud.uni-muenchen.de> (raw)
The following is a design sketch of a simple and efficient pseudo-random
bit generator that has successfully passed U. M. Maurer's universal
statistical test for random bit generators [1].
(a) Use a good PRNG that produces a real-valued sequence (y_i)
(i = 1,2,....) of uniform distribution in [0,1).
(b) Form the 24-bit integer sequence (z_i) with z_i := 2^24 * y_i which
provides the blocks (3 bytes) of pseudo-random bits desired.
For the PRNG in (a) we choose to use the compound PRNG designed by the
author in [2] which is based on the idea of randomly interlacing the
outputs of a number of constituent PRNGs (see below for the algorithm).
With L=8, Q=5000, K=1000000 (in Maurer's notation) we obtained in an
experiment the following values of the test parameter ftu, with n
denoting the number of constituent generators of our compound PRNG.
The max, min and mean values are with respect to 100 test runs done for
each value of n (each run with a different compound PRNG).
n min ftu max ftu mean ftu
1 6.804041 7.236945 7.178144
2 7.155620 7.223903 7.184418
5 7.173252 7.193011 7.183730
10 7.177052 7.189913 7.183914
20 7.178847 7.187996 7.183980
50 7.177911 7.186389 7.183700
100 7.180321 7.186633 7.183638
200 7.181037 7.185719 7.183679
500 7.180933 7.186409 7.183587
1000 7.180637 7.186052 7.183680
For rejection rate rho=0.01 the threshold values computed from Table
1 of [1] are:
t1 = 7.180865 t2 = 7.186466
Thus it can be seen that with n of the order of 50 or larger our
scheme of pseudo-random bit generation is indeed very satisfactory.
Discussion and notes:
1. Our scheme is designed for computers having 24-bit mantissa for
real-valued numbers (32-bit word length). Thus it is from the outset
not sensible to use in (b) a multiplier of y_i larger than 2^24.
Evidently smaller multipliers would be better than larger ones. This
has in fact been verified by using sequences (y_i) of inferior
quality. That a multiplier smaller than 2^24 is not called for, as
indicated by the results of our experiment, is attributable to the
superior quality of the sequence (y_i) generated by our compound
PRNG.
2. The algorithm of the compound PRNG we used to generate (y_i) may be
very simply described as follows:
j := 0;
do output(G(j)); j := trunc(n*G(j)) od;
where G(j) (0 <= j < n) denote calls to n internal constituent PRNGs
with output in the real-valued interval [0,1). (As discussed in [2],
these n PRNGs can be fairly arbitrarily chosen, subjected only to a
few very minor constraints. In particular, the PRNGs may be of any
type.) Note that the order of activation of the n constituent PRNGs
is determined by pseudo-random numbers produced by these PRNGs
themselves and that only one half of the total outputs generated by
them appear as the output of the compound PRNG. In the experiment
reported above we have, for the sole purpose of convenience,
generated the parameters of the n constituent PRNGs using a standard
PRNG and a single seed. However, in actual applications the
parameters of the n PRNGs may all be individually specified, if
desired, thus imposing a large set of unkown values for the analyst
to infer in case n is chosen to be correspondingly large. Further
note that the computing cost factor of the compound PRNG is
independent of n, being a constant 2 with respect to one single
constituent PRNG, thus permitting liberal choice of very large values
of n with the purpose to defeat analysis and/or to obtain extremely
long period length. (For each number output by the compound PRNG
exactly 2 calls of one of the n constituent PRNGs are involved.)
3. While the n constituent PRNGs used in the experiment reported above
are based on linear congruential relations (see the program code
in [3]) the bits of the integer-valued numbers obtained from the
congruential relations are not directly used. Rather, these integers
are divided by the respective moduli of the congruential relations
to obtain real-valued numbers in the interval [0,1). It is the bits
of the 24-bit integers subsequently obtained through multiplication
by 2^24 that finally constitute the pseudo-random bits output by our
scheme. In other words, the integers output from the different
congruential relations are mapped to one and the same common range
[0,2^24-1]. The mapping effected is thus different for outputs
stemming from different constituent PRNGs because the moduli of the
congruential relations are chosen to be different by construction.
This normalization process tends to lead to a qualitatively much
better bit sequences represented by (z_i) than the n bit sequences
contained in the integers directly obtained from the congruential
relations underlying the n constituent PRNGs. It constitutes one of
the essential factors contributing to the success of our scheme, the
other factor being the random interlacing or intermixing of the
output streams of the n constituent PRNGs, a fact which is explicit
in the algorithm of the compound PRNG presented above.
4. Using a somewhat optimized program written in Fortran 90, the time
for generating 10 million bytes of pseudo-random bits using our
scheme on a 200 MHZ PC was found to be 6.4 sec.
5. The computer program used in the reported experiment may be found in
[3] and is omitted here for space reasons.
Comments, critiques and suggestions for improvement are sincerely
solicitated. My e-mail address is as follows:
mok-kong.shen@stud.uni-muenchen.de
References
[1] U. M. Maurer, A Universal Statistical Test for Random Bit
Generators, J. Cryptology (1992) 5:89-105.
[2] http://www.stud.uni-muenchen.de/~mok-kong.shen/#problem2
[3] http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper1
reply other threads:[~1998-04-07 0:00 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox