Randomizer

Randomizer.zip contains the following files:


randomizer.html         This file
randomizer.dll          Randomizer library
bbs.ave                 Example of using BlumBlumShub algorithm
bbskey.ave              Example of generating keys for BBS
moa.ave                 Example of using MotherOfAll algorithm
gonzo.ave               Benchmark example (see Comparison of Algorithms below)
source_c.zip            C++ source code for Randomizer
moa_random.ave          Avenue implementation of MotherOfAll algorithm
moa_example.ave         Example of using moa_random.ave

Randomizer.dll encapsulates seven pseudo random number algorithms:


BBS BlumBlumShub
MOA MotherOfAll
MTW MTwister
RNC RandC
RSH Ranshi
RRW RanrotW
TPR TripleRand

Each algorithm has two methods to return numbers:


XXX_GetIntegerA         Returns n where min <= n <= max
XXX_GetFloatA           Returns n where 0.0 <= n < 1.0

Two additional methods are used in initializing:


SetSeedA                Sets the seed for all algorithms except BBS
SetIntegerRangeA        Sets min and max for XXX_GetIntegerA

For all algorithms except BBS, if the seed has not been explicitly set by SetSeedA, the current time is used.

Use SetIntegerRangeA to set min and max for XXX_GetIntegerA. Otherwise, 0 will be returned.

The following methods are used in conjunction with the BBS algorithm:


BBS_InitA               Initializes the BBS generator
BBS_BlumInitA           Initializes BBS_GenBlumPrimeA and BBS_GenKeyA
BBS_GenBlumPrimeA       Generates Blum prime for BBS_InitA
BBS_GenKeyA             Generates key value for BBS_InitA

BBS must be initialized using BBS_InitA. Arguments P and Q are very large, different Blum prime numbers. (A Blum prime mod 4 equals 3.) Argument KEY is a quadratic residue mod (P*Q). If BBS_InitA has not been run, the numeric methods will return 0.

Some additional methods have been implemented to assist the user in obtaining P, Q, and KEY (see "bbskey.ave" for an example of their use):

BBS_BlumInitA initializes the FreeLIP pseudorandom number generator for BBS_GenBlumPrimeA and BBS_GenKeyA. SEED is a seed for the pseudorandom number generator. If SEED is 0, the current time is used.

BBS_GenBlumPrimeA generates a pseudorandom, highly probable (50 tests) Blum prime number for use as P or Q in BBS_InitA. (A Blum prime mod 4 equals 3.) Returns 0 if failed. The argument NUMBITS is the required number of bits for the resulting value. Run BBS_BlumInitA first.

BBS_GenKeyA generates a quadratic residue mod (P*Q) for use in BBS_InitA. Returns 0 if failed. Run BBS_BlumInitA first. Adapted from the bc code by Jeffrey I. Schiller [ http://www.mit.edu/afs/net.mit.edu/dapps/mit/jis/random/].

Description of Algorithms

BlumBlumShub (BBS) is an implementation of the quadratic residue algorithm published by Blum, Blum, and Shub for the generation of cryptographically strong random numbers. For more info see: [ http://www.mit.edu/afs/net.mit.edu/dapps/mit/jis/random/]. For large integer math, the code utilizes the freeLIP package designed by Arjen K. Lenstra and currently supported by Paul Leyland [ ftp://sable.ox.ac.uk/pub/math/].

MotherOfAll (MOA) is taken from the Mother of All code by Agner Fog [ http://www.agner.org/random/].

MTwister (MTW) is an implementation of the Mersenne Twister algorithm by M. Matsumoto and T. Nishimura, adapted from the C code at: [ http://www.math.keio.ac.jp/~matumoto/emt.html].

RandC (RNC) uses the standard C++ library rand function.

Ranshi (RSH) is an implementation of the Ranshi algorithm by F. Gutbrod, adapted from the Fermilab HEP Random library at: [ http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/CLHEP/doc/html/CLHEP-random.html].

RanrotW (RRW) is taken from the RANROT W code by Agner Fog [ http://www.agner.org/random/].

TripleRand (TPR) is an implementation of the TripleRand algorithm, adapted from the Fermilab HEP Random library at: [ http://www.fnal.gov/docs/working-groups/fpcltf/Pkg/CLHEP/doc/html/CLHEP-random.html].

Comparison of Algorithms

10000000 random bytes were generated using ArcView's random number generator plus each algorithm in Randomizer (see "gonzo.ave"). The program ENT was used to analyze the results of each. For more information on ENT see: [ http://www.fourmilab.ch/random/]. The results are presented below.


Algorithm      Run Time   Arith Mean   Chi Square   Exceed    Correlation    Entropy

ArcView             616       127.49     19841.74     0.01      -0.000061   7.998256
BlumBlumShub      25899       127.47       243.05       50      -0.000084   7.999982
MotherOfAll         814       127.52       266.63       50       0.000575   7.999981
MTwister            808       127.52       270.93       25       0.000304   7.999980
RandC               816       127.48       261.50       50       0.000208   7.999981
Ranshi              806       127.47       249.56       50      -0.000174   7.999982
RanrotW             806       127.51       238.13       75      -0.000245   7.999983
TripleRand          805       127.51       208.30     97.5       0.000429   7.999985

Run Time = run time in seconds on a dual PIII 700 machine

Arith Mean = arithmetic mean (127.5 = random)

Chi Square = chi square distribution for 100000 samples

Exceed = the percent of times the chi square distribution would exceed this value (50 is random, values closer to 0 or 100 are less random)

Correlation = serial correlation coefficient (totally uncorrelated = 0.0)

Entropy = entropy in bits per byte (8.0 is maximum)

While the arithmetic mean, correlation, and entropy scores are good for all algorithms, ArcView fails miserably in the chi square test. TripleRand has the next worst score, and MTwister and RanrotW are marginal.

Another series of tests were performed using the program DIEHARD. For more information on DIEHARD see: [ http://stat.fsu.edu/~geo/diehard.html]. The results are given below:


Test                ArcView  BlumBlumShub  MotherOfAll  MTwister  RandC  Ranshi  RanrotW  TripleRand

Birthday spacings     0.420         0.248        0.245     0.718  0.730   0.245    0.386      0.934
OPERM5[1]             0.780         0.026[4]     0.243     0.573  0.162   0.516    0.965      0.534
Binary rank 31x31     0.429         0.568        0.955     0.329  0.356   0.636    0.973      0.321
Binary rank 32x32     0.633         0.967        0.743     0.508  0.470   0.936    0.707      0.705
Binary rank 6x8       1.000         0.292        0.787     0.640  0.112   0.471    0.567      0.740
Bitstream[2]          1.000         0.915        0.835     0.146  0.000   0.184    0.967      0.270
OPSO[2]               1.000         0.304        0.118     0.451  1.000   0.637    0.586      0.790
OQSO[2]               1.000         0.495        0.340     0.819  1.000   0.026    0.172      0.036
DNA[2]                1.000         0.905        0.667     0.107  1.000   0.218    0.380      0.480
1's successive[1]     0.969         0.687        0.368     0.243  0.253   0.879    0.208      0.010
1's specific[2]       0.298         0.695        0.960     0.437  0.430   0.757    0.545      0.827
Parking lot           0.771         0.762        0.556     0.666  0.222   0.473    0.619      0.637
Minimum distance      0.666         0.744        0.782     0.461  0.793   0.586    0.483      0.581
3D spheres            0.286         0.341        0.133     0.120  0.863   0.552    0.558      0.782
Squeeze               0.901         0.487        0.413     0.336  0.303   0.683    0.140      0.453
Overlapping sums      0.834         0.640        0.466     0.243  0.966   0.382    0.310      0.297
Runs up[1]            0.738         0.302        0.546     0.448  0.388   0.900    0.325      0.801
Runs down[1]          0.800         0.920        0.542     0.182  0.310   0.932    0.669      0.928
Craps win             0.102         0.273        0.944     0.096  0.884   0.471    0.316      0.913
Craps throw           0.948         0.159        0.052     0.689  0.684   0.109    0.167      0.846

Tests failed[3]           5             1            0         0      4       0        0          1

[1] Result of 1st test

[2] Result of KS test on multiple p values.

[3] Assumes that if p < 0.025 or p > 0.975, the algorithm fails at the 0.05 level.

[4] The second score is 0.000.

BlumBlumShub, while a favorite in the cryptographic community, is by far the worst in terms of run time. The next slowest algorithm runs in 3% of the time. Granted, the choice of FreeLIP as the large number library may be a factor. Nonetheless, the fact that other, far more efficient algorithms have comparable or better randomness scores would pretty much rule this out as an algorithm for scientific applications.

Of the remaining algorithms, putting equal weight on ENT and DIEHARD, MotherOfAll and Ranshi show the best overall randomness.

MotherOfAll Avenue Script

Because ArcView consumes memory when making numerous DLLProc calls, and because the MotherOfAll algorithm may readily be implemented in Avenue, "moa_random.ave" is provided as a good quality, easy-to-use random number generator. The run time is slower (5710 seconds for 10000000 bytes), but the randomness is comparable to the C++ implementation.