num_bigint/
bigrand.rs

Help
1//! Randomization of big integers
2#![cfg(feature = "rand")]
3#![cfg_attr(docsrs, doc(cfg(feature = "rand")))]
4
5use rand::distributions::uniform::{SampleBorrow, SampleUniform, UniformSampler};
6use rand::prelude::*;
7
8use crate::BigInt;
9use crate::BigUint;
10use crate::Sign::*;
11
12use crate::biguint::biguint_from_vec;
13
14use num_integer::Integer;
15use num_traits::{ToPrimitive, Zero};
16
17/// A trait for sampling random big integers.
18///
19/// The `rand` feature must be enabled to use this. See crate-level documentation for details.
20pub trait RandBigInt {
21    /// Generate a random [`BigUint`] of the given bit size.
22    fn gen_biguint(&mut self, bit_size: u64) -> BigUint;
23
24    /// Generate a random [ BigInt`] of the given bit size.
25    fn gen_bigint(&mut self, bit_size: u64) -> BigInt;
26
27    /// Generate a random [`BigUint`] less than the given bound. Fails
28    /// when the bound is zero.
29    fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
30
31    /// Generate a random [`BigUint`] within the given range. The lower
32    /// bound is inclusive; the upper bound is exclusive. Fails when
33    /// the upper bound is not greater than the lower bound.
34    fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
35
36    /// Generate a random [`BigInt`] within the given range. The lower
37    /// bound is inclusive; the upper bound is exclusive. Fails when
38    /// the upper bound is not greater than the lower bound.
39    fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
40}
41
42fn gen_bits<R: Rng + ?Sized>(rng: &mut R, data: &mut [u32], rem: u64) {
43    // `fill` is faster than many `gen::<u32>` calls
44    rng.fill(data);
45    if rem > 0 {
46        let last = data.len() - 1;
47        data[last] >>= 32 - rem;
48    }
49}
50
51impl<R: Rng + ?Sized> RandBigInt for R {
52    cfg_digit!(
53        fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
54            let (digits, rem) = bit_size.div_rem(&32);
55            let len = (digits + (rem > 0) as u64)
56                .to_usize()
57                .expect("capacity overflow");
58            let mut data = vec![0u32; len];
59            gen_bits(self, &mut data, rem);
60            biguint_from_vec(data)
61        }
62
63        fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
64            use core::slice;
65
66            let (digits, rem) = bit_size.div_rem(&32);
67            let len = (digits + (rem > 0) as u64)
68                .to_usize()
69                .expect("capacity overflow");
70            let native_digits = Integer::div_ceil(&bit_size, &64);
71            let native_len = native_digits.to_usize().expect("capacity overflow");
72            let mut data = vec![0u64; native_len];
73            unsafe {
74                // Generate bits in a `&mut [u32]` slice for value stability
75                let ptr = data.as_mut_ptr() as *mut u32;
76                debug_assert!(native_len * 2 >= len);
77                let data = slice::from_raw_parts_mut(ptr, len);
78                gen_bits(self, data, rem);
79            }
80            #[cfg(target_endian = "big")]
81            for digit in &mut data {
82                // swap u32 digits into u64 endianness
83                *digit = (*digit << 32) | (*digit >> 32);
84            }
85            biguint_from_vec(data)
86        }
87    );
88
89    fn gen_bigint(&mut self, bit_size: u64) -> BigInt {
90        loop {
91            // Generate a random BigUint...
92            let biguint = self.gen_biguint(bit_size);
93            // ...and then randomly assign it a Sign...
94            let sign = if biguint.is_zero() {
95                // ...except that if the BigUint is zero, we need to try
96                // again with probability 0.5. This is because otherwise,
97                // the probability of generating a zero BigInt would be
98                // double that of any other number.
99                if self.gen() {
100                    continue;
101                } else {
102                    NoSign
103                }
104            } else if self.gen() {
105                Plus
106            } else {
107                Minus
108            };
109            return BigInt::from_biguint(sign, biguint);
110        }
111    }
112
113    fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
114        assert!(!bound.is_zero());
115        let bits = bound.bits();
116        loop {
117            let n = self.gen_biguint(bits);
118            if n < *bound {
119                return n;
120            }
121        }
122    }
123
124    fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint {
125        assert!(*lbound < *ubound);
126        if lbound.is_zero() {
127            self.gen_biguint_below(ubound)
128        } else {
129            lbound + self.gen_biguint_below(&(ubound - lbound))
130        }
131    }
132
133    fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt {
134        assert!(*lbound < *ubound);
135        if lbound.is_zero() {
136            BigInt::from(self.gen_biguint_below(ubound.magnitude()))
137        } else if ubound.is_zero() {
138            lbound + BigInt::from(self.gen_biguint_below(lbound.magnitude()))
139        } else {
140            let delta = ubound - lbound;
141            lbound + BigInt::from(self.gen_biguint_below(delta.magnitude()))
142        }
143    }
144}
145
146/// The back-end implementing rand's [`UniformSampler`] for [`BigUint`].
147#[derive(Clone, Debug)]
148pub struct UniformBigUint {
149    base: BigUint,
150    len: BigUint,
151}
152
153impl UniformSampler for UniformBigUint {
154    type X = BigUint;
155
156    #[inline]
157    fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
158    where
159        B1: SampleBorrow<Self::X> + Sized,
160        B2: SampleBorrow<Self::X> + Sized,
161    {
162        let low = low_b.borrow();
163        let high = high_b.borrow();
164        assert!(low < high);
165        UniformBigUint {
166            len: high - low,
167            base: low.clone(),
168        }
169    }
170
171    #[inline]
172    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
173    where
174        B1: SampleBorrow<Self::X> + Sized,
175        B2: SampleBorrow<Self::X> + Sized,
176    {
177        let low = low_b.borrow();
178        let high = high_b.borrow();
179        assert!(low <= high);
180        Self::new(low, high + 1u32)
181    }
182
183    #[inline]
184    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
185        &self.base + rng.gen_biguint_below(&self.len)
186    }
187
188    #[inline]
189    fn sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X
190    where
191        B1: SampleBorrow<Self::X> + Sized,
192        B2: SampleBorrow<Self::X> + Sized,
193    {
194        rng.gen_biguint_range(low.borrow(), high.borrow())
195    }
196}
197
198impl SampleUniform for BigUint {
199    type Sampler = UniformBigUint;
200}
201
202/// The back-end implementing rand's [`UniformSampler`] for [`BigInt`].
203#[derive(Clone, Debug)]
204pub struct UniformBigInt {
205    base: BigInt,
206    len: BigUint,
207}
208
209impl UniformSampler for UniformBigInt {
210    type X = BigInt;
211
212    #[inline]
213    fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
214    where
215        B1: SampleBorrow<Self::X> + Sized,
216        B2: SampleBorrow<Self::X> + Sized,
217    {
218        let low = low_b.borrow();
219        let high = high_b.borrow();
220        assert!(low < high);
221        UniformBigInt {
222            len: (high - low).into_parts().1,
223            base: low.clone(),
224        }
225    }
226
227    #[inline]
228    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
229    where
230        B1: SampleBorrow<Self::X> + Sized,
231        B2: SampleBorrow<Self::X> + Sized,
232    {
233        let low = low_b.borrow();
234        let high = high_b.borrow();
235        assert!(low <= high);
236        Self::new(low, high + 1u32)
237    }
238
239    #[inline]
240    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
241        &self.base + BigInt::from(rng.gen_biguint_below(&self.len))
242    }
243
244    #[inline]
245    fn sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X
246    where
247        B1: SampleBorrow<Self::X> + Sized,
248        B2: SampleBorrow<Self::X> + Sized,
249    {
250        rng.gen_bigint_range(low.borrow(), high.borrow())
251    }
252}
253
254impl SampleUniform for BigInt {
255    type Sampler = UniformBigInt;
256}
257
258/// A random distribution for [`BigUint`] and [`BigInt`] values of a particular bit size.
259///
260/// The `rand` feature must be enabled to use this. See crate-level documentation for details.
261#[derive(Clone, Copy, Debug)]
262pub struct RandomBits {
263    bits: u64,
264}
265
266impl RandomBits {
267    #[inline]
268    pub fn new(bits: u64) -> RandomBits {
269        RandomBits { bits }
270    }
271}
272
273impl Distribution<BigUint> for RandomBits {
274    #[inline]
275    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigUint {
276        rng.gen_biguint(self.bits)
277    }
278}
279
280impl Distribution<BigInt> for RandomBits {
281    #[inline]
282    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt {
283        rng.gen_bigint(self.bits)
284    }
285}
num_bigint/bigrand.rs

num_bigint/
bigrand.rs
