1 /* mpz_urandomm (rop, state, n) -- Generate a uniform pseudorandom
2 integer in the range 0 to N-1, using STATE as the random state
3 previously initialized by a call to gmp_randinit().
5 Copyright 2000, 2002 Free Software Foundation, Inc.
7 This file is part of the GNU MP Library.
9 The GNU MP Library is free software; you can redistribute it and/or modify
10 it under the terms of the GNU Lesser General Public License as published by
11 the Free Software Foundation; either version 3 of the License, or (at your
12 option) any later version.
14 The GNU MP Library is distributed in the hope that it will be useful, but
15 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
16 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
17 License for more details.
19 You should have received a copy of the GNU Lesser General Public License
20 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
24 #include "longlong.h" /* for count_leading_zeros */
27 #define MAX_URANDOMM_ITER 80
30 mpz_urandomm (mpz_ptr rop
, gmp_randstate_t rstate
, mpz_srcptr n
)
33 mp_size_t nbits
, size
;
43 nlast
= &PTR (n
)[size
- 1];
45 /* Detect whether n is a power of 2. */
46 pow2
= POW2_P (*nlast
);
48 for (np
= PTR (n
); np
< nlast
; np
++)
51 pow2
= 0; /* Mark n as `not a power of two'. */
55 count_leading_zeros (count
, *nlast
);
56 nbits
= size
* GMP_NUMB_BITS
- (count
- GMP_NAIL_BITS
) - pow2
;
57 if (nbits
== 0) /* nbits == 0 means that n was == 1. */
68 tp
= TMP_ALLOC_LIMBS (size
);
69 MPN_COPY (tp
, np
, size
);
73 /* Here the allocated size can be one too much if n is a power of
74 (2^GMP_NUMB_BITS) but it's convenient for using mpn_cmp below. */
75 rp
= MPZ_REALLOC (rop
, size
);
76 /* Clear last limb to prevent the case in which size is one too much. */
79 count
= MAX_URANDOMM_ITER
; /* Set iteration count limit. */
82 _gmp_rand (rp
, rstate
, nbits
);
83 MPN_CMP (cmp
, rp
, np
, size
);
85 while (cmp
>= 0 && --count
!= 0);
88 /* Too many iterations; return result mod n == result - n */
89 mpn_sub_n (rp
, rp
, np
, size
);
91 MPN_NORMALIZE (rp
, size
);