Random number generators | www.agner.org

Begin New Subject | Threaded View | Search | List | List Messageboards | Help |

the math behind mother - Perderabo - 2004-11-24 |

the math behind mother - Agner - 2004-11-25 |

the math behind mother - Perderabo - 2004-11-25 |

the math behind mother - Agner - 2004-11-26 |

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: |

Reply To This Message |

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. |

Reply To This Message |

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 |

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. |

Reply To This Message |

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: The first 3 integers are the multipliers. The next integer is the connection integer. And finally the period. 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! |

Reply To This Message |

Begin New Subject | Threaded View | Search | List | List Messageboards | Help |