third_party/rust/num-bigint/src/bigrand.rs

   1 //! Randomization of big integers
   2
   3 use rand::distributions::uniform::{SampleUniform, UniformSampler};
   4 use rand::prelude::*;
   5 use rand::AsByteSliceMut;
   6
   7 use BigInt;
   8 use BigUint;
   9 use Sign::*;
  10
  11 use big_digit::BigDigit;
  12 use bigint::{into_magnitude, magnitude};
  13
  14 use integer::Integer;
  15 use traits::Zero;
  16
  17 pub trait RandBigInt {
  18     /// Generate a random `BigUint` of the given bit size.
  19     fn gen_biguint(&mut self, bit_size: usize) -> BigUint;
  20
  21     /// Generate a random BigInt of the given bit size.
  22     fn gen_bigint(&mut self, bit_size: usize) -> BigInt;
  23
  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;
  27
  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;
  32
  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;
  37 }
  38
  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
  48         // desired.
  49         data.to_le();
  50         if rem > 0 {
  51             data[digits] >>= BITS - rem;
  52         }
  53         BigUint::new(data)
  54     }
  55
  56     fn gen_bigint(&mut self, bit_size: usize) -> BigInt {
  57         loop {
  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.
  66                 if self.gen() {
  67                     continue;
  68                 } else {
  69                     NoSign
  70                 }
  71             } else if self.gen() {
  72                 Plus
  73             } else {
  74                 Minus
  75             };
  76             return BigInt::from_biguint(sign, biguint);
  77         }
  78     }
  79
  80     fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
  81         assert!(!bound.is_zero());
  82         let bits = bound.bits();
  83         loop {
  84             let n = self.gen_biguint(bits);
  85             if n < *bound {
  86                 return n;
  87             }
  88         }
  89     }
  90
  91     fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint {
  92         assert!(*lbound < *ubound);
  93         if lbound.is_zero() {
  94             self.gen_biguint_below(ubound)
  95         } else {
  96             lbound + self.gen_biguint_below(&(ubound - lbound))
  97         }
  98     }
  99
 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)))
 106         } else {
 107             let delta = ubound - lbound;
 108             lbound + BigInt::from(self.gen_biguint_below(magnitude(&delta)))
 109         }
 110     }
 111 }
 112
 113 /// The back-end implementing rand's `UniformSampler` for `BigUint`.
 114 #[derive(Clone, Debug)]
 115 pub struct UniformBigUint {
 116     base: BigUint,
 117     len: BigUint,
 118 }
 119
 120 impl UniformSampler for UniformBigUint {
 121     type X = BigUint;
 122
 123     #[inline]
 124     fn new(low: Self::X, high: Self::X) -> Self {
 125         assert!(low < high);
 126         UniformBigUint {
 127             len: high - &low,
 128             base: low,
 129         }
 130     }
 131
 132     #[inline]
 133     fn new_inclusive(low: Self::X, high: Self::X) -> Self {
 134         assert!(low <= high);
 135         Self::new(low, high + 1u32)
 136     }
 137
 138     #[inline]
 139     fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
 140         &self.base + rng.gen_biguint_below(&self.len)
 141     }
 142
 143     #[inline]
 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)
 146     }
 147 }
 148
 149 impl SampleUniform for BigUint {
 150     type Sampler = UniformBigUint;
 151 }
 152
 153 /// The back-end implementing rand's `UniformSampler` for `BigInt`.
 154 #[derive(Clone, Debug)]
 155 pub struct UniformBigInt {
 156     base: BigInt,
 157     len: BigUint,
 158 }
 159
 160 impl UniformSampler for UniformBigInt {
 161     type X = BigInt;
 162
 163     #[inline]
 164     fn new(low: Self::X, high: Self::X) -> Self {
 165         assert!(low < high);
 166         UniformBigInt {
 167             len: into_magnitude(high - &low),
 168             base: low,
 169         }
 170     }
 171
 172     #[inline]
 173     fn new_inclusive(low: Self::X, high: Self::X) -> Self {
 174         assert!(low <= high);
 175         Self::new(low, high + 1u32)
 176     }
 177
 178     #[inline]
 179     fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
 180         &self.base + BigInt::from(rng.gen_biguint_below(&self.len))
 181     }
 182
 183     #[inline]
 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)
 186     }
 187 }
 188
 189 impl SampleUniform for BigInt {
 190     type Sampler = UniformBigInt;
 191 }
 192
 193 /// A random distribution for `BigUint` and `BigInt` values of a particular bit size.
 194 #[derive(Clone, Copy, Debug)]
 195 pub struct RandomBits {
 196     bits: usize,
 197 }
 198
 199 impl RandomBits {
 200     #[inline]
 201     pub fn new(bits: usize) -> RandomBits {
 202         RandomBits { bits }
 203     }
 204 }
 205
 206 impl Distribution<BigUint> for RandomBits {
 207     #[inline]
 208     fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigUint {
 209         rng.gen_biguint(self.bits)
 210     }
 211 }
 212
 213 impl Distribution<BigInt> for RandomBits {
 214     #[inline]
 215     fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt {
 216         rng.gen_bigint(self.bits)
 217     }
 218 }