1 //! Randomization of big integers
3 use rand::distributions::uniform::{SampleUniform, UniformSampler};
5 use rand::AsByteSliceMut;
11 use big_digit::BigDigit;
12 use bigint::{into_magnitude, magnitude};
17 pub trait RandBigInt {
18 /// Generate a random `BigUint` of the given bit size.
19 fn gen_biguint(&mut self, bit_size: usize) -> BigUint;
21 /// Generate a random BigInt of the given bit size.
22 fn gen_bigint(&mut self, bit_size: usize) -> BigInt;
24 /// Generate a random `BigUint` less than the given bound. Fails
25 /// when the bound is zero.
26 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
28 /// Generate a random `BigUint` within the given range. The lower
29 /// bound is inclusive; the upper bound is exclusive. Fails when
30 /// the upper bound is not greater than the lower bound.
31 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
33 /// Generate a random `BigInt` within the given range. The lower
34 /// bound is inclusive; the upper bound is exclusive. Fails when
35 /// the upper bound is not greater than the lower bound.
36 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
39 impl<R: Rng + ?Sized> RandBigInt for R {
40 fn gen_biguint(&mut self, bit_size: usize) -> BigUint {
41 use super::big_digit::BITS;
42 let (digits, rem) = bit_size.div_rem(&BITS);
43 let mut data = vec![BigDigit::default(); digits + (rem > 0) as usize];
44 // `fill_bytes` is faster than many `gen::<u32>` calls
45 self.fill_bytes(data[..].as_byte_slice_mut());
46 // Swap bytes per the `Rng::fill` source. This might be
47 // unnecessary if reproducibility across architectures is not
51 data[digits] >>= BITS - rem;
56 fn gen_bigint(&mut self, bit_size: usize) -> BigInt {
58 // Generate a random BigUint...
59 let biguint = self.gen_biguint(bit_size);
60 // ...and then randomly assign it a Sign...
61 let sign = if biguint.is_zero() {
62 // ...except that if the BigUint is zero, we need to try
63 // again with probability 0.5. This is because otherwise,
64 // the probability of generating a zero BigInt would be
65 // double that of any other number.
71 } else if self.gen() {
76 return BigInt::from_biguint(sign, biguint);
80 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
81 assert!(!bound.is_zero());
82 let bits = bound.bits();
84 let n = self.gen_biguint(bits);
91 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint {
92 assert!(*lbound < *ubound);
94 self.gen_biguint_below(ubound)
96 lbound + self.gen_biguint_below(&(ubound - lbound))
100 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt {
101 assert!(*lbound < *ubound);
102 if lbound.is_zero() {
103 BigInt::from(self.gen_biguint_below(magnitude(&ubound)))
104 } else if ubound.is_zero() {
105 lbound + BigInt::from(self.gen_biguint_below(magnitude(&lbound)))
107 let delta = ubound - lbound;
108 lbound + BigInt::from(self.gen_biguint_below(magnitude(&delta)))
113 /// The back-end implementing rand's `UniformSampler` for `BigUint`.
114 #[derive(Clone, Debug)]
115 pub struct UniformBigUint {
120 impl UniformSampler for UniformBigUint {
124 fn new(low: Self::X, high: Self::X) -> Self {
133 fn new_inclusive(low: Self::X, high: Self::X) -> Self {
134 assert!(low <= high);
135 Self::new(low, high + 1u32)
139 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
140 &self.base + rng.gen_biguint_below(&self.len)
144 fn sample_single<R: Rng + ?Sized>(low: Self::X, high: Self::X, rng: &mut R) -> Self::X {
145 rng.gen_biguint_range(&low, &high)
149 impl SampleUniform for BigUint {
150 type Sampler = UniformBigUint;
153 /// The back-end implementing rand's `UniformSampler` for `BigInt`.
154 #[derive(Clone, Debug)]
155 pub struct UniformBigInt {
160 impl UniformSampler for UniformBigInt {
164 fn new(low: Self::X, high: Self::X) -> Self {
167 len: into_magnitude(high - &low),
173 fn new_inclusive(low: Self::X, high: Self::X) -> Self {
174 assert!(low <= high);
175 Self::new(low, high + 1u32)
179 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
180 &self.base + BigInt::from(rng.gen_biguint_below(&self.len))
184 fn sample_single<R: Rng + ?Sized>(low: Self::X, high: Self::X, rng: &mut R) -> Self::X {
185 rng.gen_bigint_range(&low, &high)
189 impl SampleUniform for BigInt {
190 type Sampler = UniformBigInt;
193 /// A random distribution for `BigUint` and `BigInt` values of a particular bit size.
194 #[derive(Clone, Copy, Debug)]
195 pub struct RandomBits {
201 pub fn new(bits: usize) -> RandomBits {
206 impl Distribution<BigUint> for RandomBits {
208 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigUint {
209 rng.gen_biguint(self.bits)
213 impl Distribution<BigInt> for RandomBits {
215 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt {
216 rng.gen_bigint(self.bits)