Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Notice that nowadays, unlike 2 years ago, people usually recommend to use the last technique I presented there in the last paragraph before the Conclusion. Which is to generate a random value that is big enough, so that n-log(p) > 128 so that the bias will be too small to be exploitable in practice. It's simpler and unlike rejection sampling ensures your code cannot fall into an infinite loop in case your PRNG is broken. (I'd argue you might want your code to fail in that case anyway, but YMMV.)


The other virtue of this technique is that some of the more popular fast rejection sampling methods (e.g. Lemire's "nearly divisionless") leak a small amount of information via timing side channel, because the divisionless fast path is _not_ unbiased.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: