Random number generators | www.agner.org
Begin New Subject | Flat View | Search | List | List Messageboards | Help |
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 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: Anyone of these generators is pretty awesome. And now I'm well on my way to writing a really good password generator. |
Reply To This Message | Previous Message | Next Message |
the math behind mother new - Perderabo - 2004-11-24 |
the math behind mother new - Agner - 2004-11-25 |
the math behind mother - Perderabo - 2004-11-25 |
the math behind mother new - Agner - 2004-11-26 |
the math behind mother new - Perderabo - 2004-12-18 |
Begin New Subject | Flat View | Search | List | List Messageboards | Help |