Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:33 ADT
Mok-Kong Shen (mok-kong.shen@stud.uni-muenchen.de)
Fri, 17 Jul 1998 13:27:40 +0100
In [1] I designed a simple compound PRNG which consists in pseudo-
randomly activating an arbitrarily given number n of PRNGs delivering
in [0,1), the sequence of activation of these consitituent generators
being determined by their own output. More precisely, each constituent
generator upon being selected first generates a number in [0,1) to
become the output of the compound PRNG and then generates a second
number in [0,1) to determine the constituent generator that is to be
activated next. As demonstrated in [2], the compound PRNG can be used to
obtain random bit streams that successfully pass Maurer's test [3].
There is, however, one deficiency with this design which stems from
the fact that one or a few of the n constituent generators (which are
assumed to be fairly arbitrarily chosen, i.e. subject only to very mild
selection constraints) may happen to be quite poor statistically.
Suppose the 0-th constituent generator is very poor and it has a
subsequence of its output consisting of values all in the vicinity of 0.
Then once it is selected (while it is at the position of the said
subsequence) it will continue to be selected for a number of times
(depending on the length of the subsequence) according to the algorithm
in [1]. Analogous situations can arise to any of the n constituent
generators. Although with some care in selecting the constituent
generators the probability of this happening can be greatly reduced, it
is apparently desirable that this 'hole' be closed in view of its
eventual consequences. A simple remedy is to insert a check into the
algorithm in [1] as follows:
j1:=g(j)*n;
if j1=j then j:=(j+1) mod n else j:=j1 fi;
In my implementation in [1] the constituent generators are all
internally based on linear congruential relations of the form:
X[new] = a * X[old] + b (mod c)
If a, b and c are fairly randomly chosen (as I did there), the chance
of obtaining rather small period lengths of the constituent generators
can be sufficiently high so as to require a larger number of n for
obtaining a desired magnitude of the period length of the compound PRNG.
It is therefore considered to be desirable to tighten up the selection
criteria of the parameters of the congruential relations so as to obtain
some more or less optimal period lengths of the individual constituent
generators. For that purpose we choose to make use of the following
simple theorem (instead of the theorem of Hull and Dobell [4], p.17,
which appears to be less useful for our situation):
THEOREM. If c is an odd prime and a is a primitive root of c then
the period length of the generator
X[new] = a * X[old] + b (mod c)
is either 1 (for a unique special seed X') or c-1 (for any seed unequal
to X').
We omit the proof, since for b=0 it is a special case of a theorem on
multiplicative LCPRNG (see [4], p.20) and for b<>0 the proof is also
quite straightforward. Note on the other hand that the theorem in the
present form appears not have been stated in the literature on pseudo-
random number generation, e.g. [4 - 9], known to me. Indeed, in [4],
p.184, it is even stated (apparently for the case b <> 0) that the seed
may be chosen arbitrarily, while according to the above theorem we have
to exercise care to avoid the one particular seed X' (dependent on a, b
and c) that leads to the pathological case of period length of 1.
(Example: a = 11, b = 100, c = 281, X' = 271).
In view of this theorem our selection criteria of the n constituent
generators have been revised to the following:
1. c be a prime between 1000000 and 10000000.
2. b be a pseudo-random integer in [0, c-1].
3. a >= 30 (to avoid too poor serial correlations).
4. a be a primitive root of c (to obtain the optimal period c-1).
5. Computing X should never lead to overflow (maxint = 2^31-1).
6. The seed be a pseudo-random number in [0, c-1]. The one special
seed X' that leads to the pathological case with period 1 is to
be avoided.
In [10] I designed a simple stream encoding stream where the output
sequence obtained from a PRNG -- a multiple seed version of the PRNG
of Park and Miller [11], as suggested in [12] -- is further processed
by (1) passing it through a shuffling buffer according to the method of
Bays and Durham [13] and (2) combining two numbers output from the
shuffling buffer into one number through addition mod 1, which is a
technique employed by Wichmann and Hill [14,15] in the design of their
compound PRNG. As both of these, especially (2), evidently render
the inference of the original sequence from the post-processed sequence
extremely difficult (one has to guess from the result of addition mod 1
the two (pseudo-random) participating addends -- I am yet ignorant of
how this could be effectively done), the ensemble of the seeds of the
PRNG that the user input is reasonably secure against analysis. Since
my compound PRNG, as mentioned in [1], has its design goal to serve not
only normal numerical computations but also information security
applications, I have employed the same multiple seed PRNG (with post-
processing) to construct the n constituent generators of the compound
PRNG.
The revised implementation of my compound PRNG in Fortran 90 is
available as part of my encoding software WEAK3 published in [16].
It may be extracted for independent use from the tail part of the
programm listing there. (The code is a bit lengthy due to computation
of primitive roots.)
Critiques, comments and suggestions for improvement are sincerely
solicited.
M. K. Shen
LITERATURE
[1] http://www.stud.uni-muenchen.de/~mok-kong.shen/#problem2
[2] http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper1
[3] U. M. Maurer, A universal statistical test for random bit
generators, J. Cryptology (1992) 5:89-105.
[4] D. E. Knuth, The art of computer programming. Vol. 2, 3rd ed.
Addison-Wesley, 1998.
[5] J. Dagpunar, Principles of random variate generation.
Clarendon, 1988.
[6] G. S. Fishman, Monte Carlo. Springer, 1996.
[7] R. D. Ripley, The lattice structure of pseudo-random number
generators. Proc. R. Soc. Lond. A 389 (1983) 197-204.
[8] P. L'Ecuyer, Uniform random number generation. Ann. Op. Res.
53 (1994) 77-120.
[9] P. L'Ecuyer, Random number generation. In J. Banks (ed.) Handbook
on simulation. Wiley, 1998.
[10] http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper7
(revised 16th July 1998)
[11] S. K. Park, K. W. Miller, Random number generators: good ones
are hard to find. Comm. ACM 31 (1988) 1192-1201.
[12] http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper4
[13] C. Bays, S. D. Durham, Improving a poor random number generator.
ACM Trans. Math. Software 2 (1976) 59-64.
[14] B. A. Wichmann, I. D. Hill, A pseudo-random number generator.
NPL Report, DITC 6/82, June 1982.
[15] B. A. Wichmann, I. D. Hill, An efficient and portable pseudo-
random number generator. Appl. Stat. 31 (1982) 188-190.
[16] http://www.stud.uni-muenchen.de/~mok-kong.shen/#paper10
The following archive was created by hippie-mail 7.98617-22 on Fri Aug 21 1998 - 17:20:33 ADT