Random number generators discussion

Random number generators | www.agner.org

the math behind mother
Author:  Date: 2004-11-25 20:58
Let's go through the steps to design a RWC. The first thing to nail down what I call the modulus of the generator. I want a modulus of 100000 which means that my generator will spit out integers in the range of 0 through 99999. Having made that decision, this means that I am destined to have a intermediate result which maxes out at 100000^2-1 or 9999999999. I have the luxury of not caring. But that may not be true all the time. Mother is designed for a 64 bit intermediate result which result in a 32 bit modulus. (What I call the modulus, Masaglia calls the base.) There is nothing sacred about always being a power of 2 or a ower of 10. For example, say I have signed 32 bit arithmetic. My largest intermediate result is 2^31 = 2147483648. The square root of that is about 46430 ( 46430^2 = 214739560), so it might make sense to settle on an output modulus of 46430. You need to consider the modulus and the intermediate result pretty much at the same time. But you can make any choice work.

Having picked a modulus, I will have placed some constraints on my multipliers. Consider a simple multiply with carry: s = a*x + c
In the worst case, my X might be 99999 with the same value for my carry. That multiplier needs to 99999 or less since 99999*99999+99999 = 9999900000. Any more and I might overflow. Now the worst case in a RWC is similar: s = (a1+a2+a3+a4)*x + c. The rule is the sum of the multipliers must be less than the modulus.

Our next choice is really what I call the number of stages. But again we sort of need to pick our multipliers at the same time. The more stages the better. More stages means a longer period. And it means more initial states (a "wider" seed). The price to be paid comes in form of larger and larger primes to factor. In my case, I wanted to use 64 bit unsigned arithmetic to factor my primes. This really became the limiting factor. Let's say that my first multiplier is 98765 and my number of stages is 3. I need to calculate what Marsaglia calls m. Other researchers call it the connection integer. Just for my first multipler alone I am at 98765 * 100000^3 = 98765000000000000000 and that is too large...I have exceeded 2^64. So I must pull in my horns a bit here. 9999*100000^3 = 9999000000000000000 which will fit in a 64 bit integer. Since I have 3 stages, I need two more multipliers. I want something easy to remember, so out of the blue I pick: 9876. This get multiplied by the modulus to the second power. 9999*10000^3 + 9876*100000^2 = 9999098760000000000. Note that the magnitude of the connection integer is really controlled by the first multiplier. That's why we want it to be as large as possible. I cannot pick my final mutiplier at will....I must find it. I will start with 2 and calculate the final connection integer: 9999*10000^3 + 9876*100000^2 + 2 * 100000 - 1 = 9999098760000199999.

So that is where we start looking. We must test 9999098760000199999 to see if it's prime. Next we test 9999098760000299999. And so on. Even if we find a prime, we only have a candidate. We then must check (m-1)/2 = period. The period integer must also be prime. I stopped with with a third multiplier of 9999 but I could have kept going to 99999 - (9999+9876) = 80124. Even so, it took about 3 days to find:
## 9999 9876 222 9,999,098,760,022,199,999 4,999,549,380,011,099,999
## 9999 9876 900 9,999,098,760,089,999,999 4,999,549,380,044,999,999
## 9999 9876 936 9,999,098,760,093,599,999 4,999,549,380,046,799,999
## 9999 9876 1257 9,999,098,760,125,699,999 4,999,549,380,062,849,999
## 9999 9876 1929 9,999,098,760,192,899,999 4,999,549,380,096,449,999
## 9999 9876 2244 9,999,098,760,224,399,999 4,999,549,380,112,199,999
## 9999 9876 3612 9,999,098,760,361,199,999 4,999,549,380,180,599,999
## 9999 9876 3630 9,999,098,760,362,999,999 4,999,549,380,181,499,999
## 9999 9876 4992 9,999,098,760,499,199,999 4,999,549,380,249,599,999
## 9999 9876 5097 9,999,098,760,509,699,999 4,999,549,380,254,849,999
## 9999 9876 5583 9,999,098,760,558,299,999 4,999,549,380,279,149,999
## 9999 9876 6771 9,999,098,760,677,099,999 4,999,549,380,338,549,999
## 9999 9876 7221 9,999,098,760,722,099,999 4,999,549,380,361,049,999
## 9999 9876 7425 9,999,098,760,742,499,999 4,999,549,380,371,249,999
## 9999 9876 7737 9,999,098,760,773,699,999 4,999,549,380,386,849,999
## 9999 9876 8355 9,999,098,760,835,499,999 4,999,549,380,417,749,999
## 9999 9876 8799 9,999,098,760,879,899,999 4,999,549,380,439,949,999
## 9999 9876 8988 9,999,098,760,898,799,999 4,999,549,380,449,399,999
## 9999 9876 9009 9,999,098,760,900,899,999 4,999,549,380,450,449,999
## 9999 9876 9150 9,999,098,760,914,999,999 4,999,549,380,457,499,999
## 9999 9876 9249 9,999,098,760,924,899,999 4,999,549,380,462,449,999
## 9999 9876 9909 9,999,098,760,990,899,999 4,999,549,380,495,449,999

Anyone of these generators is pretty awesome. And now I'm well on my way to writing a really good password generator.

 
thread the math behind mother new - Perderabo - 2004-11-24
last replythread the math behind mother new - Agner - 2004-11-25
last replythread the math behind mother - Perderabo - 2004-11-25
last replythread the math behind mother new - Agner - 2004-11-26
last reply the math behind mother new - Perderabo - 2004-12-18