next up previous
Next: Packing and Unpacking RNG Up: The RNG Random Number Previous: 262 -216 + 1


The Cryptographic Hash Function

We use a cryptographic hash function to construct an initial random number state from a pair of integers, or from a parent random number state for a child particle. Block encryption functions are perfectly good for this, themselves providing random numbers of good quality that are uncorrelated with linear congruential recurrence relations. The encryption key provides a means for the user to easily create a different random instance of the problem run, affecting the starting values for all of the particles in the application. The current crop of block encryption functions operating on 64 bits match our choice of a 64-bit unsigned integer for random number state quite nicely.

The fact that an encryption algorithm is reversible is not essential, but does assure that the hash function provides a random, one-to-one, shuffle of the random number states produced by the generator. This property is guaranteed in the case of the 64-bit linear congruential generator, where the random number state is a full 64-bit value. Output collisions can occur in the other generators that do not fully use all possible 64-bit values, but the probability of such collisions is low.

Any block encryption algorithm of sufficient quality will suffice as our random hash function for random number state generation. We have chosen the encryption algorithm IDEA [6] [7] because of its efficient portable implementation on general purpose computers. The IDEA encryption algorithm is comprised of 8 rounds of a Feistel network, mixing the operations of three 16-bit wide algebraic groups to scramble the result. We have found that two rounds of IDEA produces a suitably random output from its input, and that four rounds would offer an adequate safety margin against correlations being detectable between parent and child random number states produced by the hash function. The full 8 rounds of IDEA are available for the truly paranoid Monte Carlo practitioner. The user can adjust the number of rounds of IDEA used, in response to performance needs, in the event that the costs of random number state generation become significant. The number of rounds of IDEA used can be adjusted from 1, to the full 8 rounds, with 4 rounds being the default.

The IDEA encryption algorithm employs a key of 128 bits. A default key is provided. This key was randomly chosen using dice. The subroutine that sets the IDEA key in our library takes two 32-bit integers provided as arguments by the user and constructs the 128-bit IDEA key by exclusive or'ing this 64 bits with the upper and lower 64 bits of the default key. It is very difficult, if not impossible, for the user to generate a bad choice for the encryption key. The default encryption key is the same as the one generated if the user passes zeros to RngSetKey.

The functions to control the properties of the hash function are: void RngSetKey( Rng_UInt32 k1, Rng_UInt32 k2 )

void RngSetKeyRounds( int n ) Here, Rng_UInt32 is a 32-bit unsigned integer and is defined in the header file rng.h. The RngSetKey() and RngSetKeyRounds() functions are used for all of the random number generators provided. The RngSetKeyRounds() function sets the number of rounds of IDEA used in the hash function, silently enforcing the range 1 through 8.

RngSetKeyRounds() and RngSetKey() may be called in any order, but must, if used, be called before the other RNG routines are called. RngSetKeyRounds() does not have to be called, in which case the default value for the number of rounds is 4. The full IDEA encryption algorithm uses 8 rounds, but our tests have shown that changing a single bit avalanches with good randomness to all of the output bits in just two rounds. Since this was an empirical test, we added two more rounds to the default for a safety margin. Setting the number of rounds higher than 4 will slow down the process of seed generation, but should result in less correlation between the input and output. Setting the number of rounds to 1 produces clear evidence of correlations, but may be sufficiently random for applications where the speed of seed generation is paramount. Generally, the code developer should not expose control of the number of rounds to the user, who might easily set it too low without carefully checking statistical properties of application results.


next up previous
Next: Packing and Unpacking RNG Up: The RNG Random Number Previous: 262 -216 + 1