Timeline for How to determine seed collision probability in a PRNG?
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 18, 2018 at 4:54 | comment | added | D.W.♦ | The second comment does not appear to be a correct summary of the relevance of the birthday paradox here. | |
| Aug 18, 2018 at 4:52 | comment | added | D.W.♦ | @bryc, right, but (1) in that case the collision probability is not low enough, and (2) in any case the real problem is not the possibility of collisions; the problem is a much more fundamental one (e.g., that the set of possible outputs is too small). Focusing on collisions is focusing on just one thing that can go wrong, but on the list of things that are likely to go wrong, it's pretty far down the list, compared to a lot of other possibilities. | |
| Aug 18, 2018 at 2:09 | comment | added | bryc | The issue is, collision probabilities grow exponentially the more times you run the random generation (birthday problem). 128-bit hashes for example have "low enough" probabilities, but this can be a problem when a PRNG only uses 32/31 bits in a seed such as LCG, or if for some reason two different seeds produce the same sequence. | |
| Aug 18, 2018 at 1:42 | comment | added | bryc | It does matter. I can use a PRNG to generate 256 bits of random data but if the PRNG's seed is 31 bits (such as in an Lehmer LCG) only a small fraction of the possible outcomes can be accessed. If I generate a 128-bit random seed, I want all those bits incorporated in the PRNG and that collisions only occur when the seed itself collides! | |
| Aug 18, 2018 at 0:00 | history | answered | D.W.♦ | CC BY-SA 4.0 |