mpz_urandomm

[Jason Moxham]

In the current mpz_urandom we have this bit of code

count = MAX_URANDOMM_ITER; /* Set iteration count limit. */
do
{
_gmp_rand (rp, rstate, nbits);// generate n bits uniform distro
MPN_CMP (cmp, rp, np, size);
}
while (cmp >= 0 && --count != 0);

if (count == 0)
/* Too many iterations; return result mod n == result - n */
mpn_sub_n (rp, rp, np, size);

This clearly violates the uniform random distribution of results , although
as MAX_URAMDOM_ITER is 80 , it is by a very small amount. I can't think of
any good reason to keep this. Unless there is a good reason to put it in , I
will not do this for the mpn version , and will also remove it from this mpz
version

Jason

[Jason Moxham]

However without this hack , it does fail the tests/rand/urndmm.c tests in this
part

/* Test that mpz_urandomm returns the correct result with a
broken LC. */
mpz_set_ui (a, 0L);
gmp_randinit_lc_2exp (r1, a, 0xffL, 8L);
mpz_set_ui (m, 5L);
/* Warning: This code hangs in gmp 4.1 and below */
for (i = 0; i < 100; i++)
{printf("tring %d\n",i);fflush(0);
mpz_urandomm (a, r1, m);
if (mpz_cmp_ui (a, 2L) != 0)
{
result = FALSE;
gmp_printf ("mpz_urandomm returns %Zd instead of 2\n", a);
break;
}
}
gmp_randclear (r1);

with

- Function: void gmp_randinit_lc_2exp (gmp_randstate_t STATE, mpz_t
A, unsigned long C, unsigned long M2EXP)
Initialize STATE with a linear congruential algorithm X = (A*X +
C) mod 2^M2EXP.

The low bits of X in this algorithm are not very random. The least
significant bit will have a period no more than 2, and the second
bit no more than 4, etc. For this reason only the high half of
each X is actually used.

When a random number of more than M2EXP/2 bits is to be generated,
multiple iterations of the recurrence are used and the results
concatenated.

Now this a linear congruent generator with sequence
x' = x*0+255 mod 256

This doesn't make any sense , if it is a lc generator then dont choose such a
dumb/redundant one , and if it is not a lc generator then again dont choose
such a dumb one.

I'm going to take this test out, or does it make sense?

Jason