reproducibility of GMP random functions vs limb size and GMP version

Torbjorn Granlund tg at
Fri Sep 17 11:23:59 CEST 2010

Paul Zimmermann <Paul.Zimmermann at> writes:

  > mpz_urandomm extracts the exact number of random bits necessary to
  > accomodate the given limit, exactly as mpz_urandomb does. If the result
  > is greater than or equal to the limit, all bits are discarded and a new
  > extraction is performed. There is a limit to the iteration count to
  > prevent ill generators from locking GMP.
  does it mean that if N=2^n+1 for large n, and I call mpz_urandomm with
  modulus N, we will most likely hit the limit?
In that scenario, the likelyhood for another iteration is close to
0.5-epsilon.  IIRC, GMP uses up to 80 iterations.  I leave it as an
exercise to the reader to trigger this limit in the next 50 years.

(Note that triggering he limit is no complete disaster, it just results
in a slightly skewed random distribution.)


More information about the gmp-devel mailing list