Tuesday, September 27, 2016

[tmgjbmah] GMP mpz_urandomm nonuniform

The GNU MP function mpz_urandomm tries rejection sampling up to 80 times (MAX_URANDOMM_ITER) to find a random number which fits within the user-specified range.  Each attempt I think fails with probability at most 1/2, so the probability of 80 consecutive failures is around 0.5^80, an extremely small number.

After 80 failures, it silently uses mod to bring the too large number into range, which destroys the uniformity.  I think it should instead abort, because 80 consecutive failures means something deeper is going wrong, perhaps a faulty random number generator which only emits '111...'.

No comments :