Random number generators discussion

Random number generators | www.agner.org

 
thread the math behind mother - Perderabo - 2004-11-24
last replythread the math behind mother - Agner - 2004-11-25
last replythread the math behind mother - Perderabo - 2004-11-25
last replythread the math behind mother - Agner - 2004-11-26
last reply the math behind mother - Perderabo - 2004-12-18
 
the math behind mother
Author:  Date: 2004-11-24 20:02
I have made good progress over the past few months in understanding the math behind the Recursion With Carry generator. In particular I know how to design one and compute its period. There are two initial states that collapse instantly to a period of one. I can find the non-zero trivial state as well. First you need to calculate an integer:
((2^32)^4)*2111111111 + ((2^32)^3)*1492 + ((2^32)^2)*1776 + (2^32)*5115 - 1 =
718373885684172166973216179348278232025854377983
(2^32 is the base of the generator. ) This integer must be a prime. Marsaglia calls this integer m. If m is a prime, the period will be some number that can even divide (m-1)/2. That integer is:
359186942842086083486608089674139116012927188991
If this is also a prime, then m is called a safe prime. The period will either be the huge number above or 1.

All zeros will repeat forever with a period of 1. You already know that. But set the Carry to 2111119493 and all 4 X's to 4294967295 and the generator will also have a period of 1. I believe that this is the only other case where the generator has a period of 1. These numbers come from:
2111119493 = (2111111111 + 1492 + 1776 + 5115) -1
4294967295 = (2^32) - 1

   
the math behind mother
Author:  Date: 2004-11-25 10:10
Interesting. I didn't know there was a second degenerate state. Marsaglia hasn't documented the math too well.

Are you able to construct similar generators with base 2^16 or 2^64 or with a different number of terms? A generator with one term less may be implemented in a particularly efficient way in assembly language.

   
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.

   
the math behind mother
Author:  Date: 2004-11-26 06:02
Thanks for the explanation.
I just want you to know that division is very slow, even on modern computers. The modulo computations require division if the modulus is not a power of 2. That's why we prefer a modulus which is a power of 2. Best is 2^16, 2^32, or 2^64 because it fits a computer word size so all computations are modulo the word size.
   
the math behind mother
Author:  Date: 2004-12-18 21:27
Well I have some good news and some bad news. First, I have finished my password generator and it is available here: www.unix.com/showthread.php?s=&threadid=16116 It can generate passwords according to a template. I asked for hexadecimal passwords 80 characters long. And I generated one million of them. The resulting data file passed diehard. At last, I have my password generator.

One of the generators you wanted, a 2^16 with three terms can be designed with my 64 bit tools. Here are some that I found:
61111 1234 4180 17,201,222,602,028,482,559 8,600,611,301,014,241,279
61111 1234 4465 17,201,222,602,047,160,319 8,600,611,301,023,580,159
61111 1234 5233 17,201,222,602,097,491,967 8,600,611,301,048,745,983
61111 1234 5290 17,201,222,602,101,227,519 8,600,611,301,050,613,759
61111 1234 5965 17,201,222,602,145,464,319 8,600,611,301,072,732,159
61111 1234 6025 17,201,222,602,149,396,479 8,600,611,301,074,698,239

The first 3 integers are the multipliers. The next integer is the connection integer. And finally the period.
Now for the bad news. A Multiply with Carry is strickly periodic, but a Recursion with Carry is eventually periodic. A sequence can have a leader before it becomes periodic. Marsaglia calls these rho sequences. I have found a rho sequence that leads to a period of one.
Xmother[0]=4294967295
Xmother[1]=4294967295
Xmother[2]=4294967295
Xmother[3]=4294967294
Cmother=4222230604

The carry is rather large....that is guaranteed to be the case. If the carry is less than the sum of the multipliers, it will stay there. So I now initialize the carry modulo the sum of the multipiers. And actually, that is what Marsaglia suggests. Once I figure something out, I always seem to be able to find it in Marsaglia's paper. But he certainly isn't as explicit as he could be.

Happy Holidays!